Mining Billion%2DNode Graphs Patterns%2C Generators and Tools.

Analysis of Large Multi%2Dmodal Social Networks Patterns and a Generator.

Surprising Patterns for the Call Duration Distribution of Mobile Phone Users.
Abstract. How long are the phone calls of mobile users? What are the chances of a call to end, given its current duration? Here we answer these questions by studying the call duration distributions (CDDs) of individual users in large mobile networks. We analyzed a large, real network of 3.1 million users and more than one billion phone call records from a private mobile phone company of a large city, spanning0.1TB. Our first contribution is the TLAC distribution to fit the CDD of each user; TLAC is the truncated version of so-called log-logistic distribution, a skewed, power-law-like distribution. We show that the TLAC is an excellent fit for the overwhelming majority of our users (more than 96 % of them), much better than exponential or lognormal. Our second contribution is the MetaDist to model the collective behavior of the users given their CDDs. We show that the MetaDist distribution accurately and succinctly describes the calls duration behavior of users in large mobile networks. All of our methods are fast, and scale linearly with the number of customers. 1
Virus Propagation on Time%2DVarying Networks Theory and Immunization Algorithms.

Finding Clusters in subspaces of very large%2C multi%2Ddimensional datasets.

Fast algorithms for time series mining.

Metric forensics a multi%2Dlevel approach for mining volatile graphs.


TWave High%2DOrder Analysis of Spatiotemporal Data.


EigenSpokes Surprising Patterns and Scalable Community Chipping in Large Graphs.

BASSET Scalable Gateway Finder in Large Graphs.

Radius Plots for Mining Tera%2Dbyte Scale Graphs Algorithms
Given large, multi-million node graphs (e.g., FaceBook, web-crawls, etc.), how do they evolve over time? How are they connected? What are the central nodes and the outliers of the graphs? We show that the Radius Plot (pdf of node radii) can answer these questions. However, computing the Radius Plot is prohibitively expensive for graphs reaching the planetary scale. There are two major contributions in this paper: (a) We propose HADI (HAdoop DIameter and radii estimator), a carefully designed and fine-tuned algorithm to compute the diameter of massive graphs, that runs on the top of the HADOOP /MAPREDUCE system, with excellent scale-up on the number of available machines (b) We run HADI on several real world datasets including YahooWeb (6B edges, 1/8 of a Terabyte), one of the largest public graphs ever analyzed. Thanks to HADI, we report fascinating patterns on large networks, like the surprisingly small effective diameter, the multi-modal/bi-modal shape of the Radius Plot, and its palindrome motion over time. 1
HCDF A Hybrid Community Discovery Framework.

SPEX2 automated concise extraction of spatial gene expression patterns from Fly embryo ISH images.



Time series analysis with multiple resolutions.

Fast Feature Selection using Fractal Dimension %2D Ten Years Later.

Fast feature selection using fractal dimension.
Dimensionalitycurse and dimensionality reduction are two issues that have retained high interest for data mining, machine learning, multimedia indexing, and clustering. We present a fast, scalable algorithm to quickly select the most important attributes (dimensions) for a given set of n-dimensional vectors. In contrast to older methods, our method has the following desirable properties: (a) it does not do rotation of attributes, thus leading to easy interpretation of the resulting attributes; (b) it can spot attributes that have nonlinear correlations; (c) it requires a constant number of passes over the dataset; (d) it gives a good estimate on how many attributes we should keep.  The idea is to use the `fractal&#039; dimension of a dataset as a good approximation of its intrinsic dimension, and to drop attributes that do not affect it. We applied our method on real and synthetic datasets, where it gave fast and good results.  1 - Introduction and Motivation  Whenmanaging the increasing vo...
Kronecker Graphs An Approach to Modeling Networks.

Parsimonious Linear Fingerprinting for Time Series.
We study the problem of mining and summarizing multiple time series effectively and efficiently. We propose PLiF, a novel method to discover essential characteristics (“fingerprints”), by exploiting the joint dynamics in numerical sequences. Our fingerprinting method has the following benefits: (a) it leads to interpretable features; (b) it is versatile: PLiF enables numerous mining tasks, including clustering, compression, visualization, forecasting, and segmentation, matching top competitors in each task; and (c) it is fast and scalable, with linear complexity on the length of the sequences. We did experiments on both synthetic and real datasets, including human motion capture data (17MB of human motions), sensor data (166 sensors), and network router traffic data (18 million raw updates over 2 years). Despite its generality, PLiF outperforms the top clustering methods on clustering; the top compression methods on compression (3 times better reconstruction error, for the same compression ratio); it gives meaningful visualization and at the same time, enjoys a linear scale-up. 1.
Spectral Counting of Triangles in Power%2DLaw Networks via Element%2DWise Sparsification.

SHIFTR a user%2Ddirected

SHIFTR a user%2Ddirected

iPoG fast interactive proximity querying on graphs.

Graph Mining Patterns%2C Generators and Tools.

RTG A Recursive Realistic Graph Generator Using Random Typing.
We propose a new, recursive model to generate realistic graphs, evolving over time. Our model has the following properties: it is (a) flexible, capable of generating the cross product of weighted/unweighted, directed/undirected, uni/bipartite graphs; (b) realistic, giving graphs that obey eleven static and dynamic laws that real graphs follow (we formally prove that for several of the (power) laws and we estimate their exponents as a function of the model parameters); (c) parsimonious, requiring only four parameters. (d) fast, being linear on the number of edges; (e) simple, intuitively leading to the generation of macroscopic patterns. We empirically show that our model mimics two real-world graphs very well: Blognet (unipartite, undirected, unweighted) with 27K nodes and 125K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23K nodes and 880K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar. 1
PEGASUS A Peta%2DScale Graph Mining System.
Abstract—In this paper, we describe PEGASUS, an open source Peta Graph Mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node and finding the connected components. As the size of graphs reaches several Giga-, Tera- or Peta-bytes, the necessity for such a library grows too. To the best of our knowledge, PEGASUS is the first such library, implemented on the top of the HADOOP platform, the open source version of MAPREDUCE. Many graph mining operations (PageRank, spectral clustering, diameter estimation, connected components etc.) are essentially a repeated matrix-vector multiplication. In this paper we describe a very important primitive for PEGASUS, called GIM-V (Generalized Iterated Matrix-Vector multiplication). GIM-V is highly optimized, achieving (a) good scale-up on the number of available machines (b) linear running time on the number of edges, and (c) more than 5 times faster performance over the non-optimized version of GIM-V. Our experiments ran on M45, one of the top 50 supercomputers in the world. We report our findings on several real graphs, including one of the largest publicly available Web Graphs, thanks to Yahoo!, with ≈ 6,7 billion edges. Keywords-PEGASUS; graph mining; hadoop I.
EigenSpokes Surprising Patterns and Scalable Community Chipping in Large Graphs.

Modeling Blog Dynamics.
How do blogs produce posts? What local, underlying mechanisms lead to the bursty temporal behaviors observed in blog networks? Earlier work analyzed network patterns of blogs and found that blog behavior is bursty and often follows power laws in both topological and temporal characteristics. However, no intuitive and realistic model has yet been introduced, that can lead to such patterns. This is exactly the focus of this work. We propose a generative model that uses simple and intuitive principles for each individual blog, and yet it is able to produce the temporal characteristics of the blogosphere together with global topological network patterns, like power-laws for degree distributions, for inter-posting times, and several more. Our model ZC uses a novel ‘zero-crossing ’ approach based on a random walk, combined with other powerful ideas like exploration and exploitation. This makes it the first model to simultaneously model the topology and temporal dynamics of the blogosphere. We validate our model with experiments on a large collection of 45,000 blogs and 2.2 million posts. 1
SNARE a link analytic system for graph labeling and risk detection.
Classifying nodes in networks is a task with a wide range of applications. It can be particularly useful in anomaly and fraud detection. Many resources are invested in the task of fraud detection due to the high cost of fraud, and being able to automatically detect potential fraud quickly and precisely allows human investigators to work more efficiently. Many data analytic schemes have been put into use; however, schemes that bolster link analysis prove promising. This work builds upon the belief propagation algorithm for use in detecting collusion and other fraud schemes. We propose an algorithm called SNARE (Social Network Analysis for Risk Evaluation). By allowing one to use domain knowledge as well as link knowledge, the method was very successful for pinpointing misstated accounts in our sample of general ledger data, with a significant improvement over the default heuristic in true positive rates, and a lift factor of up to 6.5 (more than twice that of the default heuristic). We also apply SNARE to the task of graph labeling in general on publicly-available datasets. We show that with only some information about the nodes themselves in a network, we get surprisingly high accuracy of labels. Not only is SNARE applicable in a wide variety of domains, but it is also robust to the choice of parameters and highly scalable– linearly with the number of edges in a graph.
BGP%2Dlens patterns and anomalies in internet routing updates.
The Border Gateway Protocol (BGP) is one of the fundamental computer communication protocols. Monitoring and mining BGP update messages can directly reveal the health and stability of Internet routing. Here we make two contributions: firstly we find patterns in BGP updates, like self-similarity, power-law and lognormal marginals; secondly using these patterns, we find anomalies. Specifically, we develop BGP-lens, an automated BGP updates analysis tool, that has three desirable properties: (a) It is effective, able to identify phenomena that would otherwise go unnoticed, such as a peculiar ‘clothesline ’ behavior or prolonged ‘spikes ’ that last as long as 8 hours; (b) It is scalable, using algorithms that are all linear on the number of time-ticks; and (c) It is admin-friendly, giving useful leads for phenomenon of interest. We showcase the capabilities of BGP-lens by identifying surprising phenomena verified by syadmins, over a massive trace of BGP updates spanning 2 years, from the publicly available site datapository.net.
Large human communication networks patterns and a utility%2Ddriven generator.

DynaMMo mining and summarization of coevolving sequences with missing values.
Given multiple time sequences with missing values, we propose DynaMMo which summarizes, compresses, and finds latent variables. The idea is to discover hidden variables and learn their dynamics, making our algorithm able to function even when there are missing values. We performed experiments on both real and synthetic datasets spanning several megabytes, including motion capture sequences and chlorine levels in drinking water. We show that our proposed DynaMMo method (a) can successfully learn the latent variables and their evolution; (b) can provide high compression for little loss of reconstruction accuracy; (c) can extract compact but powerful features for segmentation, interpretation, and forecasting; (d) has complexity linear on the duration of sequences.
DynaMMo mining and summarization of coevolving sequences with missing values.
Given multiple time sequences with missing values, we propose DynaMMo which summarizes, compresses, and finds latent variables. The idea is to discover hidden variables and learn their dynamics, making our algorithm able to function even when there are missing values. We performed experiments on both real and synthetic datasets spanning several megabytes, including motion capture sequences and chlorine levels in drinking water. We show that our proposed DynaMMo method (a) can successfully learn the latent variables and their evolution; (b) can provide high compression for little loss of reconstruction accuracy; (c) can extract compact but powerful features for segmentation, interpretation, and forecasting; (d) has complexity linear on the duration of sequences.
BBM bayesian browsing model from petabyte%2Dscale data.
Given a quarter of petabyte click log data, how can we estimate the relevance of each URL for a given query? In this paper, we propose the Bayesian Browsing Model (BBM), a new modeling technique with following advantages: (a) it does exact inference; (b) it is single-pass and parallelizable; (c) it is effective. We present two sets of experiments to test model effectiveness and efficiency. On the first set of over 50 million search instances of 1.1 million distinct queries, BBM outperforms the state-of-the-art competitor by 29.2 % in loglikelihood while being 57 times faster. On the second clicklog set, spanning a quarter of petabyte data, we showcase the scalability of BBM: we implemented it on a commercial MapReduce cluster, and it took only 3 hours to compute the relevance for 1.15 billion distinct query-URL pairs.
TANGENT a novel%2C %27Surprise me%27%2C recommendation algorithm.

DOULION counting triangles in massive graphs with a coin.
Counting the number of triangles in a graph is a beautiful algorithmic problem which has gained importance over the last years due to its significant role in complex network analysis. Metrics frequently computed such as the clustering coefficient and the transitivity ratio involve the execution of a triangle counting algorithm. Furthermore, several interesting graph mining applications rely on computing the number of triangles in the graph of interest. In this paper, we focus on the problem of counting triangles in a graph. We propose a practical method, out of which all triangle counting algorithms can potentially benefit. Using a straightforward triangle counting algorithm as a black box, we performed 166 experiments on real-world networks and on synthetic datasets as well, where we show that our method works with high accuracy, typically more than 99 % and gives significant speedups, resulting in even ≈ 130 times faster performance.
ShatterPlots Fast Tools for Mining Large Graphs.

Click chain model in web search.
Given a terabyte click log, can we build an efficient and effective click model? It is commonly believed that web search click logs are a gold mine for search business, because they reflect users ’ preference over web documents presented by the search engine. Click models provide a principled approach to inferring user-perceived relevance of web documents, which can be leveraged in numerous applications in search businesses. Due to the huge volume of click data, scalability is a must. We present the click chain model (CCM), which is based on a solid, Bayesian framework. It is both scalable and incremental, perfectly meeting the computational challenges imposed by the voluminous click logs that constantly grow. We conduct an extensive experimental study on a data set containing 8.8 million query sessions obtained in July 2008 from a commercial search engine. CCM consistently outperforms two state-of-the-art competitors in a number of metrics, with over 9.7 % better log-likelihood, over 6.2 % better click perplexity and much more robust (up to 30%) prediction of the first and the last clicked position.
RTG a recursive realistic graph generator using random typing.
We propose a new, recursive model to generate realistic graphs, evolving over time. Our model has the following properties: it is (a) flexible, capable of generating the cross product of weighted/unweighted, directed/undirected, uni/bipartite graphs; (b) realistic, giving graphs that obey eleven static and dynamic laws that real graphs follow (we formally prove that for several of the (power) laws and we estimate their exponents as a function of the model parameters); (c) parsimonious, requiring only four parameters. (d) fast, being linear on the number of edges; (e) simple, intuitively leading to the generation of macroscopic patterns. We empirically show that our model mimics two real-world graphs very well: Blognet (unipartite, undirected, unweighted) with 27K nodes and 125K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23K nodes and 880K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar. 1
A novel optimization approach to efficiently process aggregate similarity queries in metric access methods.

Fast mining of complex time%2Dstamped events.
Given a collection of complex, time-stamped events, how do we find patterns and anomalies? Events could be meetings with one or more persons with one or more agenda items at zero or more locations (e.g., teleconferences), or they could be publications with authors,
Unsupervised modeling of object categories using link analysis techniques.

Two Heads Better Than One Pattern Discovery in Time%2DEvolving Multi%2Daspect Data.

Hierarchical%2C Parameter%2DFree Community Discovery.
Abstract. Given a large bipartite graph (like document-term, or userproduct graph), how can we find meaningful communities, quickly, and automatically? We propose to look for community hierarchies, with communities-within-communities. Our proposed method, the Context-specific Cluster Tree (CCT) finds such communities at multiple levels, with no user intervention, based on information theoretic principles (MDL). More specifically, it partitions the graph into progressively more refined subgraphs, allowing users to quickly navigate from the global, coarse structure of a graph to more focused and local patterns. As a fringe benefit, and also as an additional indication of its quality, it also achieves better compression than typical, non-hierarchical methods. We demonstrate its scalability and effectiveness on real, large graphs. 1
Using Utility to Provision Storage Systems.
Provisioning a storage system requires balancing the costs of the solution with the benefits that the solution will provide. Previous provisioning approaches have started with a fixed set of requirements and the goal of automatically finding minimum cost solutions to meet them. Such approaches neglect the cost-benefit analysis of the purchasing decision. Purchasing a storage system involves an extensive set of trade-offs between metrics such as purchase cost, performance, reliability, availability, power, etc. Increases in one metric have consequences for others, and failing to account for these trade-offs can lead to a poor return on the storage investment. Using a collection of storage acquisition and provisioning scenarios, we show that utility functions enable this cost-benefit structure to be conveyed to an automated provisioning tool, enabling the tool to make appropriate trade-offs between different system metrics including performance, data protection, and purchase cost.  
Toward a Comprehensive Model in Internet Auction Fraud Detection.
Fraud detection has become a common concern of the online auction websites. Fraudsters often manipulate reputation systems and commit nondelivery fraud. To deal with fraud in group behavior we consider network level features, such as users’ beliefs of other users. In this paper we use the loopy belief propagation algorithm and apply it to network level fraud detection, classifying fraudsters, accomplices, as well as honest users. Our method shows good classification accuracy using real data.
Monitoring Network Evolution using MDL.
Abstract — Given publication titles and authors, what can we say about the evolution of scientific topics and communities over time? Which communities shrunk, which emerged, and which split, over time? And, when in time were the turning points? We propose TimeFall, which can automatically answer these questions given a social network/graph that evolves over time. The main novelty of the proposed approach is that it needs no user-defined parameters, relying instead on the principle of Minimum Description Length (MDL), to extract the communities, and to find good cut-points in time when communities change abruptly: a cut-point is good, if it leads to shorter data description. We illustrate our algorithm on synthetic and large real datasets, and we show that the results of the TimeFall agree with human intuition. I.
RTM Laws and a Recursive Generator for Weighted Time%2DEvolving Graphs.
How do real, weighted graphs change over time? What patterns, if any, do they obey? Earlier studies focus on unweighted graphs, and, with few exceptions, they focus on static snapshots. Here, we report patterns we discover on several real, weighted, time-evolving graphs. The reported patterns can help in detecting anomalies in natural graphs, in making link prediction and in providing more criteria for evaluation of synthetic graph generators. We further propose an intuitive and easy way to construct weighted, time-evolving graphs. In fact, we prove that our generator will produce graphs which obey many patterns and laws observed to date. We also provide empirical evidence to support our claims. 1
Compact Similarity Joins.

RTM Laws and a Recursive Generator for Weighted Time%2DEvolving Graphs.
How do real, weighted graphs change over time? What patterns, if any, do they obey? Earlier studies focus on unweighted graphs, and, with few exceptions, they focus on static snapshots. Here, we report patterns we discover on several real, weighted, time-evolving graphs. The reported patterns can help in detecting anomalies in natural graphs, in making link prediction and in providing more criteria for evaluation of synthetic graph generators. We further propose an intuitive and easy way to construct weighted, time-evolving graphs. In fact, we prove that our generator will produce graphs which obey many patterns and laws observed to date. We also provide empirical evidence to support our claims. 1
GRAPHITE A Visual Query System for Large Graphs.
We present Graphite, a system that allows the user to visually construct a query pattern, finds both its exact and approximate matching subgraphs in large attributed graphs, and visualizes the matches. For example, in a social network where a person’s occupation is an attribute, the user can draw a ‘star ’ query for “finding a CEO who has interacted with a Secretary, a Manager, and an Accountant, or a structure very similar to this”. Graphite uses the G-Ray algorithm to run the query against a user-chosen data graph, gaining all of its benefits, namely its high speed, scalability, and its ability to find both exact and near matches. Therefore, for the example above, Graphite tolerates indirect paths between, say, the CEO and the Accountant, when no direct path exists. Graphite uses fast algorithms to estimate node proximities when finding matches, enabling it to scale well with the graph database size. We demonstrate Graphite’s usage and benefits using the DBLP author-publication graph, which consists of 356K nodes and 1.9M edges. A demo video of Graphite can be downloaded at
Bayesian tensor analysis.

Protein complex identification by supervised graph local clustering.

Graph mining laws%2C generators and tools.
Digital media, pervasive sensing, web authoring, mobile computing, scientific and medical instruments, physical simulations, and virtual worlds are all delivering vast new datasets relating to every aspect of our lives. A growing fraction of this Big Data is going unused or being underexploited due to the overwhelming scale of the data involved. Effective sharing, understanding, and the use of this new wealth of raw information poses a great challenges to today’s computer researchers. In order to effectively compute on this scale, many research and development groups purchase their own racks of compute and storage servers. The goal of the Tashi project is to develop a layer of utility software that turns these raw racks of servers into easily managed cloud computers that will allow remote users to share and explore their Big Data. Big Data applications are typically data hungry in that the quality of their results improves with the quantity of data available. Consequently, scalable computing technologies, able to accommodate the largest datasets possible, are important. Fortunately, these applications are usually disk bandwidth limited (rather than
Social networks looking ahead.

Using ghost edges for classification in sparsely labeled networks.
We address the problem of classification in partially labeled networks (a.k.a. within-network classification) where observed class labels are sparse. Techniques for statistical relational learning have been shown to perform well on network classification tasks by exploiting dependencies between class labels of neighboring nodes. However, relational classifiers can fail when unlabeled nodes have too few labeled neighbors to support learning (during training phase) and/or inference (during testing phase). This situation arises in realworld problems when observed labels are sparse. In this paper, we propose a novel approach to within-network classification that combines aspects of statistical relational learning and semi-supervised learning to improve classification performance in sparse networks. Our approach works by adding “ghost edges ” to a network, which enable the flow of information from labeled to unlabeled nodes. Through experiments on real-world data sets, we demonstrate that our approach performs well across a range of conditions where existing approaches, such as collective classification and semi-supervised learning, fail. On all tasks, our approach improves area under the ROC curve (AUC) by up to 15 points over existing approaches. Furthermore, we demonstrate that our approach runs in time proportional to L · E, where L is the number of labeled nodes and E is the number of edges.
Weighted graphs and disconnected components patterns and a generator.
The vast majority of earlier work has focused on graphs which are both connected (typically by ignoring all but the giant connected component), and unweighted. Here we study numerous, real, weighted graphs, and report surprising discoveries on the way in which new nodes join and form links in a social network. The motivating questions were the following: How do connected components in a graph form and change over time? What happens after new nodes join a network – how common are repeated edges? We study numerous diverse, real graphs (citation networks, networks in social media, internet traffic, and others); and make the following contributions: (a) we observe that the non-giant connected components seem to stabilize in size, (b) we observe the weights on the edges follow several power laws with surprising exponents, and (c) we propose an intuitive, generative model for graph growth that obeys observed patterns.
Cut%2Dand%2Dstitch efficient parallel learning of linear dynamical systems on smps.
Multi-core processors with ever increasing number of cores per chip are becoming prevalent in modern parallel computing. Our goal is to make use of the multi-core as well as multi-processor architectures to speed up data mining algorithms. Specifically, we present a parallel algorithm for approximate learning of Linear Dynamical Systems (LDS), also known as Kalman Filters (KF). LDSs are widely used in time series analysis such as motion capture modeling, visual tracking etc. We propose Cut-And-Stitch (CAS), a novel method to handle the data dependencies from the chain structure of hidden variables in LDS, so as to parallelize the EM-based parameter learning algorithm. We implement the algorithm using OpenMP on both a supercomputer and a quad-core commercial desktop. The experimental results show that parallel algorithms using Cut-And-Stitch achieve comparable accuracy and almost linear speedups over the serial version. In addition, Cut-And-Stitch can be generalized to other models with similar linear structures such as Hidden Markov Models (HMM) and Switching Kalman Filters (SKF).
Weighted graphs and disconnected components patterns and a generator.
The vast majority of earlier work has focused on graphs which are both connected (typically by ignoring all but the giant connected component), and unweighted. Here we study numerous, real, weighted graphs, and report surprising discoveries on the way in which new nodes join and form links in a social network. The motivating questions were the following: How do connected components in a graph form and change over time? What happens after new nodes join a network – how common are repeated edges? We study numerous diverse, real graphs (citation networks, networks in social media, internet traffic, and others); and make the following contributions: (a) we observe that the non-giant connected components seem to stabilize in size, (b) we observe the weights on the edges follow several power laws with surprising exponents, and (c) we propose an intuitive, generative model for graph growth that obeys observed patterns.
Mobile call graphs beyond power%2Dlaw and lognormal distributions.
We analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. We examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. We find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions. To analyze our observed distributions (of number of calls, distinct call partners, and total talk time), we propose PowerTrack, a method which fits a lesser known but more suitable distribution, namely the Double Pareto LogNormal (DPLN) distribution, to our data and track its parameters over time. Using PowerTrack, we find that our graph changes over time in a way consistent with a generative process that naturally results in the DPLN distributions we observe. Furthermore, we show that this generative process lends itself to a natural and appealing social wealth interpretation in the context of social networks such as ours. We discuss the application of those results to our model and to forecasting.
Colibri fast mining of large static and dynamic graphs.
Low-rank approximations of the adjacency matrix of a graph are essential in finding patterns (such as communities) and detecting anomalies. Additionally, it is desirable to track the low-rank structure as the graph evolves over time, efficiently and within limited storage. Real graphs typically have thousands or millions of nodes, but are usually very sparse. However, standard decompositions such as SVD do not preserve sparsity. This has led to the development of methods such as CUR and CMD, which seek a nonorthogonal basis by sampling the columns and/or rows of the sparse matrix. However, these approaches will typically produce overcomplete bases, which wastes both space and time. In this paper we propose the family of Colibri methods to deal with these challenges. Our version for static graphs, Colibri-S, iteratively finds a nonredundant basis and we prove that it has no loss of accuracy compared to the best competitors (CUR and CMD), while achieving significant savings in space and time: on real data, Colibri-S requires much less space and is orders of magnitude faster (in proportion to the square of the number of non-redundant columns). Additionally, we propose an efficient update algorithm for dynamic, time-evolving graphs, Colibri-D. Our evaluation on a large, real network traffic dataset shows that Colibri-D is over 100 times faster than the best published competitor (CMD).
Unsupervised modeling and recognition of object categories with combination of visual contents and geometric similarity links.

Graph Mining Laws%2C Generators and Tools.
Digital media, pervasive sensing, web authoring, mobile computing, scientific and medical instruments, physical simulations, and virtual worlds are all delivering vast new datasets relating to every aspect of our lives. A growing fraction of this Big Data is going unused or being underexploited due to the overwhelming scale of the data involved. Effective sharing, understanding, and the use of this new wealth of raw information poses a great challenges to today’s computer researchers. In order to effectively compute on this scale, many research and development groups purchase their own racks of compute and storage servers. The goal of the Tashi project is to develop a layer of utility software that turns these raw racks of servers into easily managed cloud computers that will allow remote users to share and explore their Big Data. Big Data applications are typically data hungry in that the quality of their results improves with the quantity of data available. Consequently, scalable computing technologies, able to accommodate the largest datasets possible, are important. Fortunately, these applications are usually disk bandwidth limited (rather than
Semi%2DSupervised Learning Based on Semiparametric Regularization.
Semi-supervised learning plays an important role in the recent literature on machine learning and data mining and the developed semisupervised learning techniques have led to many data mining applications in recent years. This paper addresses the semi-supervised learning problem by developing a semiparametric regularization based approach, which attempts to discover the marginal distribution of the data to learn the parametric function through exploiting the geometric distribution of the data. This learned parametric function can then be incorporated into the supervised learning on the available labeled data as the prior knowledge. Specifically, our contributions are: (1) We present a semi-supervised learning approach which incorporates the unlabeled data into the supervised learning by a parametric function learned from the whole data including the labeled and unlabeled data. The parametric function reflects the geometric structure of the marginal distribution of the data. Furthermore, the proposed approach which naturally extends to the out-of-sample data is an inductive learning method in nature. (2) This approach allows a family of algorithms to be developed based on various choices of the original RKHS and the loss function. (3) We provide experimental comparisons showing that the proposed approach leads the state-of-the-art performance on a variety of classification tasks. In particular, we demonstrate that this approach can be used successfully in both transductive and semisupervised settings. 1
Efficient Distribution Mining and Classification.
We define and solve the problem of “distribution classification”, and, in general, “distribution mining”. Given n distributions (i.e., clouds) of multi-dimensional points, we want to classify them into k classes, to find patterns, rules and out-lier clouds. For example, consider the 2-d case of sales of items, where, for each item sold, we record the unit price and quantity; then, each customer is represented as a distribution/cloud of 2-d points (one for each item he bought). We want to group similar users together, e.g., for market segmentation, anomaly/fraud detection. We propose D-Mine to achieve this goal. Our main contribution is Theorem 3.1, which shows how to use wavelets to speed up the cloud-similarity computations. Extensive experiments on both synthetic and real multidimensional data sets show that our method achieves up to 400 faster wall-clock time over the naive implementation, with comparable (and occasionally better) classification quality. 1
Proximity Tracking on Time%2DEvolving Bipartite Graphs.
Given an author-conference network that evolves over time, which are the conferences that a given author is most closely related with, and how do they change over time? Large time-evolving bipartite graphs appear in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering. Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?); and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?) Moreover, we want to do this efficiently and incrementally, and to provide “any-time ” answers. We propose pTrack and cTrack, which are based on random walk with restart, and use powerful matrix tools. Experiments on real data show that our methods are effective and efficient: the mining results agree with intuition; and we achieve up to 15∼176 times speed-up, without any quality loss. 1
Outlier%2Drobust clustering using independent components.

Graph mining and influence propagation.

Epidemic thresholds in real networks.
How will a virus propagate in a real network? How long does it take to disinfect a network given particular values of infection rate and virus death rate? What is the single best node to immunize? Answering these questions is essential for devising network-wide strategies to counter viruses. In addition, viral propagation is very similar in principle to the spread of rumors, information, and “fads, ” implying that the solutions for viral propagation would also offer insights into these other problem settings. We answer these questions by developing a nonlinear dynamical system (NLDS) that accurately models viral propagation in any arbitrary network, including real and synthesized network graphs. We propose a general epidemic threshold condition for the NLDS system: we prove that the epidemic threshold for a network is exactly the inverse of the largest eigenvalue of its adjacency matrix. Finally, we show that below the epidemic threshold, infections die out at an exponential rate. Our epidemic threshold model subsumes many known thresholds for special-case graphs (e.g., Erdös–Rényi, BA powerlaw, homogeneous). We demonstrate the predictive power of our model with extensive experiments on real and synthesized graphs, and show that our threshold condition holds for arbitrary graphs. Finally, we show how to utilize our threshold condition for practical uses: It can dictate which nodes to immunize; it can assess the effects of a throttling
Two heads better than one pattern discovery in time%2Devolving multi%2Daspect data.

Bayesian Tensor Approach for 3%2DD Face Modeling.

Random walk with restart fast solutions and applications.

C%2DDEM a multi%2Dmodal query system for Drosophila Embryo databases.
The amount of biological data publicly available has experienced an exponential growth as the technology advances. Online databases are now playing an important role as information repositories as well as easily accessible platforms for researchers to communicate and contribute. Recent research projects in image bioinformatics produce a number of databases of images, which visualize the spatial expression pattern of a gene (eg. “fj”), and most of
Less is More Sparse Graph Mining with Compact Matrix Decomposition.

Fast Monitoring Proximity and Centrality on Time%2Devolving Bipartite Graphs.

Incremental tensor analysis Theory and applications.

Data Mining Using Fractals and Power Laws.

Stream Monitoring under the Time Warping Distance.
Data stream processing has recently attracted an increasing amount of interest. The goal of this paper is to monitor numerical streams, and to find subsequences that are similar to a given query sequence, under the DTW (Dynamic Time Warping) distance. Applications include word spotting, sensor pattern matching, and monitoring of biomedical signals (e.g., EKG, ECG), and monitoring of environmental (seismic and volcanic) signals. DTW is a very popular distance measure, permitting accelerations and decelerations, and it has been studied for finite, stored sequence sets. However, in many applications such as network analysis and sensor monitoring, massive amounts of data arrive continuously and it is infeasible to save all the historical data. We propose SPRING, a novel algorithm that can solve the problem. We provide a theoretical analysis and prove that SPRING does not sacrifice accuracy, while it requires constant space and time per time-tick. These are dramatic improvements over the naive method. Our experiments on real and realistic data illustrate that SPRING does indeed detect the qualifying subsequences correctly and that it can offer dramatic improvements in speed (up to 650,000 times) over the naive implementation. 1
A Max Margin Framework on Image Annotation and Multimodal Image Retrieval.

Scalable modeling of real graphs using Kronecker multiplication.
Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? We propose to use “Kronecker graphs”, which naturally obey all of the above properties, and we present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. A naive approach to fitting would take super-exponential time. In contrast, Kron-Fit takes linear time, by exploiting the structure of Kronecker product and by using sampling. Experiments on large real and synthetic graphs show that KronFit indeed mimics very well the patterns found in the target graphs. Once fitted, the model parameters and the resulting synthetic graphs can be used for anonymization, extrapolations, and graph summarization. 1.
Probabilistic Tensor Analysis with Akaike and Bayesian Information Criteria.

Information Survival Threshold in Sensor and P2P Networks.
Abstract—Consider a network of, say, sensors, or P2P nodes, or bluetooth-enabled cell-phones, where nodes transmit information to each other and where links and nodes can go up or down. Consider also a ‘datum’, that is, a piece of information, like a report of an emergency condition in a sensor network, a national traditional song, or a mobile phone virus. How often should nodes transmit the datum to each other, so that the datum can survive (or, in the virus case, under what conditions will the virus die out)? Clearly, the link and node fault probabilities are important — what else is needed to ascertain the survivability of the datum? We propose and solve the problem using non-linear dynamical systems and fixed point stability theorems. We provide a closedform formula that, surprisingly, depends on only one additional parameter, the largest eigenvalue of the connectivity matrix. We illustrate the accuracy of our analysis on realistic and real settings, like mote sensor networks from Intel and MIT, as well as Gnutella and P2P networks. I.
Information Survival Threshold in Sensor and P2P Networks.
Abstract—Consider a network of, say, sensors, or P2P nodes, or bluetooth-enabled cell-phones, where nodes transmit information to each other and where links and nodes can go up or down. Consider also a ‘datum’, that is, a piece of information, like a report of an emergency condition in a sensor network, a national traditional song, or a mobile phone virus. How often should nodes transmit the datum to each other, so that the datum can survive (or, in the virus case, under what conditions will the virus die out)? Clearly, the link and node fault probabilities are important — what else is needed to ascertain the survivability of the datum? We propose and solve the problem using non-linear dynamical systems and fixed point stability theorems. We provide a closedform formula that, surprisingly, depends on only one additional parameter, the largest eigenvalue of the connectivity matrix. We illustrate the accuracy of our analysis on realistic and real settings, like mote sensor networks from Intel and MIT, as well as Gnutella and P2P networks. I.
Enhanced max margin learning on multimodal data mining in a multimedia database.
The problem of multimodal data mining in a multimedia database can be addressed as a structured prediction problem where we learn the mapping from an input to the structured and interdependent output variables. In this paper, built upon the existing literature on the max margin based learning, we develop a new max margin learning approach called Enhanced Max Margin Learning (EMML) framework. In addition, we apply EMML framework to developing an effective and efficient solution to the multimodal data mining problem in a multimedia database. The main contributions include: (1) we have developed a new max margin learning approach — the enhanced max margin learning framework that is much more efficient in learning with a much faster convergence rate, which is verified in empirical evaluations; (2) we have applied this EMML approach to developing an effective and efficient solution to the multimodal data mining problem that is highly scalable in the sense that the query response time is independent of the database scale, allowing facilitating a multimodal data mining querying to a very large scale multimedia database, and excelling many existing multimodal data mining methods in the literature that do not scale up at all; this advantage is also supported through the complexity analysis as well as empirical evaluations against a state-of-the-art multimodal data mining method from the literature. While EMML is a general framework, for the evaluation purpose, we apply it to the Berkeley Drosophila embryo image database, and report the performance comparison with a state-of-the-art multimodal data mining method.
Cost%2Deffective outbreak detection in networks.
� One of the networks is a spread of a disease, the other one is product recommendations � Which is which?  ☺ Diffusion in Social Networks � A fundamental process in social networks: Behaviors that cascade from node to node like an epidemic – News, opinions, rumors, fads, urban legends, … – Word‐of‐mouth effects in marketing: rise of new websites, free web based services – Virus, disease propagation – Change in social priorities: smoking, recycling – Saturation news coverage: topic diffusion among bloggers – Internet‐energized political campaigns – Cascading failures in financial markets – Localized effects: riots, people walking out of a lectureEmpirical Studies of Diffusion � Experimental studies of diffusion have long history: – Spread of new agricultural practices [Ryan‐Gross 1943] • Adoption of a new hybrid‐corn between the 259 farmers in Iowa • Classical study of diffusion • Interpersonal network plays important role in adoption � Diffusion is a social process – Spread of new medical practices [Coleman et al 1966] • Studied the adoption of a new drug between doctors in Illinois • Clinical studies and scientific evaluations were not sufficient to convince the doctors • It was the social power of peers that led to adoptionDiffusion in Networks � Initially some nodes are active � Active nodes spread their influence on the other nodes, and so on … a d
GraphScope parameter%2Dfree mining of large time%2Devolving graphs.

Fast best%2Deffort pattern matching in large attributed graphs.
We focus on large graphs where nodes have attributes, such as a social network where the nodes are labelled with each person’s job title. In such a setting, we want to find subgraphs that match a user query pattern. For example, a ‘star ’ query would be, “find a CEO who has strong interactions with a Manager, a Lawyer, and an Accountant, or another structure as close to that as possible”. Similarly, a ‘loop ’ query could help spot a money laundering ring. Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. Our method can find exact-, as well as near-matches, and it will present them to the user in our proposed ‘goodness ’ order. For example, our method tolerates indirect paths between, say, the ‘CEO ’ and the ‘Accountant ’ of the above sample query, when direct paths do not exist. Its second feature is scalability. In general, if the query has nq nodes and the data graph has n nodes, the problem needs polynomial time complexity O(n nq), which is prohibitive. Our G-Ray (“Graph X-Ray”) method finds high-quality subgraphs in time linear on the size of the data graph. Experimental results on the DLBP author-publication graph (with 356K nodes and 1.9M edges) illustrate both the effectiveness and scalability of our approach. The results agree with our intuition, and the speed is excellent. It takes 4 seconds on average for a 4node query on the DBLP graph.
Fast direction%2Daware proximity for graph mining.
In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the concept of escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straightforward implementations.
Less is More Compact Matrix Decomposition for Large Sparse Graphs.
Given a large sparse graph, how can we find patterns and anomalies? Several important applications can be modeled as large sparse graphs, e.g., network traffic monitoring, research citation network analysis, social network analysis, and regulatory networks in genes. Low rank decompositions, such as SVD and CUR, are powerful techniques for revealing latent/hidden variables and associated patterns from high dimensional data. However, those methods often ignore the sparsity property of the graph, and hence usually incur too high memory and computational cost to be practical. We propose a novel method, the Compact Matrix Decomposition (CMD), to compute sparse low rank approximations. CMD dramatically reduces both the computation cost and the space requirements over existing decomposition methods (SVD, CUR). Using CMD as the key building block, we further propose procedures to efficiently construct and analyze dynamic graphs from real-time application data. We provide theoretical guarantee for our methods, and present results on two real, large datasets, one on network flow data (100GB trace of 22K hosts over one month) and one on DBLP (200MB over 25 years). We show that CMD is often an order of magnitude more efficient than the state of the art (SVD and CUR): it is over 10X faster, but requires less than 1/10 of the space, for the same reconstruction accuracy. Finally, we demonstrate how CMD is used for detecting anomalies and monitoring timeevolving graphs, in which it successfully detects worm-like hierarchical scanning patterns in real network data. 1
Patterns of Cascading Behavior in Large Blog Graphs.
How do blogs cite and influence each other? How do such links evolve? Does the popularity of old blog posts drop exponentially with time? These are some of the questions that we address in this work. Blogs (weblogs) have become an important medium of information because of their timely publication, ease of use, and wide availability. In fact, they often make headlines, by discussing and discovering evidence about political events and facts. Often blogs link to one another, creating a publicly available record of how information and influence spreads through an underlying social network. Aggregating links from several blog posts creates a directed graph which we analyze to discover the patterns of information propagation in blogspace, and thereby understand the underlying social network. Here we report some surprising findings of the blog linking and information propagation structure, after we analyzed one of the largest available datasets, with 45, 000 blogs and ≈ 2.2 million blog-postings. Our analysis also sheds light on how rumors, viruses, and ideas propagate over social and computer networks.
Mining large graphs and streams using matrix and tensor tools.

Boosting k%2DNearest Neighbor Queries Estimating Suitable Query Radii.

Parallel crawling for online social networks.
Given a huge online social network, how do we retrieve information from it through crawling? Even better, how do we improve the crawling performance by using parallel crawlers that work independently? In this paper, we present the framework of parallel crawlers for online social networks, utilizing a centralized queue. To show how this works in practice, we describe our implementation of the crawlers for an online auction website. The crawlers work independently, therefore the failing of one crawler does not affect the others at all. The framework ensures that no redundant crawling would occur. Using the crawlers that we built, we visited a total of approximately 11 million auction users, about 66,000 of which were completely crawled.
Netprobe a fast and scalable system for fraud detection in online auction networks.
Given a large online network of online auction users and their histories of transactions, how can we spot anomalies and auction fraud? This paper describes the design and implementation of NetProbe, a system that we propose for solving this problem. NetProbe models auction users and transactions as a Markov Random Field tuned to detect the suspicious patterns that fraudsters create, and employs a Belief Propagation mechanism to detect likely fraudsters. Our experiments show that NetProbe is both efficient and effective for fraud detection. We report experiments on synthetic graphs with as many as 7,000 nodes and 30,000 edges, where NetProbe was able to spot fraudulent nodes with over 90 % precision and recall, within a matter of seconds. We also report experiments on a real dataset crawled from eBay, with nearly 700,000 transactions between more than 66,000 users, where NetProbe was highly effective at unearthing hidden networks of fraudsters, within a realistic response time of about 6 minutes. For scenarios where the underlying data is dynamic in nature, we propose Incremental NetProbe, which is an approximate, but fast, variant of Net-Probe. Our experiments prove that Incremental NetProbe executes nearly doubly fast as compared to NetProbe, while retaining over 99 % of its accuracy.

A fast and effective method to find correlations among attributes in databases.

On data mining%2C compression%2C and Kolmogorov complexity.
Abstract Will we ever have a theory of data mining analogous to the relational algebra in databases? Why do we have so many clearly different clustering algorithms? Could data mining be automated? We show that the answer to all these questions is negative, because data mining is closely related to compression and Kolmogorov complexity; and the latter is undecidable. Therefore, data mining will always be an art, where our goal will be to find better models (patterns) that fit our datasets as best as possible.
TKDE Guidelines for Survey Papers.


Graph evolution Densification and shrinking diameters.
How do real graphs evolve over time? What are &#034;normal&#034; growth patterns in  social, technological, and information networks? Many studies have discovered  patterns in static graphs, identifying properties in a single snapshot of a large  network, or in a very small number of snapshots; these include heavy tails  for in- and out-degree distributions, communities, small-world phenomena, and  others. However, given the lack of information about network evolution over  long periods, it has been hard to convert these findings into statements about  trends over time.
RIC Parameter%2Dfree noise%2Drobust clustering.

Intelligent system monitoring on large clusters.
InteMon is a prototype monitoring and mining system for large clusters. Currently, it monitors over 100 hosts of a prototype data center at CMU. It uses the SNMP protocol and it stores the monitoring data in an mySQL database. Then, it allows for visualization of the time-series data using a JSP web-based frontend interface for users. What sets it apart from other cluster monitoring systems is its ability to automatically analyze the monitoring data in real time and alert the users for potential anomalies. It uses state of the art stream mining methods, it has a sophisticated definition of anomalies (broken correlations among input streams), and it can also pinpoint the reason of the anomaly. InteMon has a user-friendly GUI, it allows the users to perform interactive mining tasks, and it is fully operational. 1.
The Omni%2Dfamily of all%2Dpurpose access methods a simple and effective way to make similarity search more efficient.

Efficient processing of complex similarity queries in RDBMS through query rewriting.

Intelligent system monitoring on large clusters.
InteMon is a prototype monitoring and mining system for large clusters. Currently, it monitors over 100 hosts of a prototype data center at CMU. It uses the SNMP protocol and it stores the monitoring data in an mySQL database. Then, it allows for visualization of the time-series data using a JSP web-based frontend interface for users. What sets it apart from other cluster monitoring systems is its ability to automatically analyze the monitoring data in real time and alert the users for potential anomalies. It uses state of the art stream mining methods, it has a sophisticated definition of anomalies (broken correlations among input streams), and it can also pinpoint the reason of the anomaly. InteMon has a user-friendly GUI, it allows the users to perform interactive mining tasks, and it is fully operational. 1.
Fast Random Walk with Restart and Its Applications.
How closely related are two nodes in a graph? How to compute this score quickly, on huge, disk-resident, real graphs? Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the “connection subgraphs”, personalized PageRank, and many more. However, the straightforward implementations of RWR do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. We propose fast solutions to this problem. The heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) blockwise, community-like structure. We exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman-Morrison lemma for matrix inversion. Experimental results on the Corel image and the DBLP dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation. 1
SuperGraph Visualization.
Given a large social or computer network, how can we visualize it, find patterns, outliers, communities? Although several graph visualization tools exist, they cannot handle large graphs with hundred thousand nodes and possibly million edges. Such graphs bring two challenges: interactive visualization demands prohibitive processing power and, even if we could interactively update the visualization, the user would be overwhelmed by the excessive number of graphical items. To cope with this problem, we propose a formal innovation on the use of graph hierarchies that leads to GMine system. GMine promotes scalability using a hierarchy of graph partitions, promotes concomitant presentation for the graph hierarchy and for the original graph, and extends analytical possibilities with the integration of the graph partitions in an interactive environment
Beyond streams and graphs dynamic tensor analysis.
How do we find patterns in author-keyword associations, evolving over time? Or in DataCubes, with product-branchcustomer sales information? Matrix decompositions, like principal component analysis (PCA) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks and many more. However, they have only two orders, like author and keyword, in the above example. We propose to envision such higher order data as tensors, and tap the vast literature on the topic. However, these methods do not necessarily scale up, let alone operate on semi-infinite streams. Thus, we introduce the dynamic tensor analysis (DTA) method, and its variants. DTA provides a compact summary for high-order and high-dimensional data, and it also reveals the hidden correlations. Algorithmically, we designed DTA very carefully so that it is (a) scalable, (b) space efficient (it does not need to store the past) and (c) fully automatic with no need for user defined parameters. Moreover, we propose STA, a streaming tensor analysis method, which provides a fast, streaming approximation to DTA. We implemented all our methods, and applied them in two real settings, namely, anomaly detection and multi-way latent semantic indexing. We used two real, large datasets, one on network flow data (100GB over 1 month) and one from DBLP (200MB over 25 years). Our experiments show that our methods are fast, accurate and that they find interesting patterns and outliers on the real datasets. 1.
Center%2Dpiece subgraphs problem definition and fast solutions.
Given Q nodes in a social network (say, authorship network), how can we find the node/author that is the centerpiece, and has direct or indirect connections to all, or most of them? For example, this node could be the common advisor, or someone who started the research area that the Q nodes belong to. Isomorphic scenarios appear in law enforcement (find the master-mind criminal, connected to all current suspects), gene regulatory networks (find the protein that participates in pathways with all or most of the given Q proteins), viral marketing and many more. Connection subgraphs is an important first step, handling the case of Q=2 query nodes. Then, the connection subgraph algorithm finds the b intermediate nodes, that provide a good connection between the two original query nodes. Here we generalize the challenge in multiple dimensions: First, we allow more than two query nodes. Second, we allow a whole family of queries, ranging from ’OR ’ to ’AND’, with ’softAND ’ in-between. Finally, we design and compare a fast approximation, and study the quality/speed trade-off. We also present experiments on the DBLP dataset. The experiments confirm that our proposed method naturally deals with multi-source queries and that the resulting subgraphs agree with our intuition. Wall-clock timing results on the DBLP dataset show that our proposed approximation achieve good accuracy for about 6: 1 speedup. This material is based upon work supported by the
Sampling from large graphs.
Given a huge real graph, how can we derive a representative sample? There are many known algorithms to compute interesting measures (shortest paths, centrality, betweenness, etc.), but several of them become impractical for large graphs. Thus graph sampling is essential.
Robust information%2Dtheoretic clustering.

Automatic mining of fruit fly embryo images.
We present FEMine, an automatic system for image-based gene expression analysis. We perform experiments on the largest publicly available collection of Drosophila ISH (in situ hybridization) images, showing that our FEMine system achieves excellent performance in classification, clustering, and content-based image retrieval. The major innovation of FEMine is the use of automatically discovered latent spatial &#034;themes&#034; of gene expressions, LGEs, in the whole-embryo context, as opposed to patterns in nearly disjoint portions of an embryo proposed in previous methods.
Distributed Pattern Discovery in Multiple Streams.
and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, or other funding parties.
Detecting Fraudulent Personalities in Networks of Online Auctioneers.
Abstract. Online auctions have gained immense popularity by creating an accessible environment for exchanging goods at reasonable prices. Not surprisingly, malevolent auction users try to abuse them by cheating others. In this paper we propose a novel method, 2-Level Fraud Spotting (2LFS), to model the techniques that fraudsters typically use to carry out fraudulent activities, and to detect fraudsters preemptively. Our key contributions are: (a) we mine user level features (e.g., number of transactions, average price of goods exchanged, etc.) to get an initial belief for spotting fraudsters, (b) we introduce network level features which capture the interactions between different users, and (c) we show how to combine both these features using a Belief Propagation algorithm over a Markov Random Field, and use it to detect suspicious patterns (e.g., unnaturally close-nit groups of people that trade mainly among themselves). Our algorithm scales linearly with the number of graph edges. Moreover, we illustrate the effectiveness of our algorithm on a real dataset collected from a large online auction site. 1
An Adaptive Two%2DPhase Approach to WiFi Location Sensing.

Evaluating the intrinsic dimension of evolving data streams.

Data Mining Using Fractals and Power Laws.

GMine A System for Scalable%2C Interactive Graph Visualization and Mining.
Several graph visualization tools exist. However, they are not able to handle large graphs, and/or they do not allow interaction. We are interested on large graphs, with hundreds of thousands of nodes. Such graphs bring two challenges: the first one is that any straightforward interactive manipulation will be prohibitively slow. The second one is sensory overload: even if we could plot and replot the graph quickly, the user would be overwhelmed with the vast volume of information because the screen would be too cluttered as nodes and edges overlap each other. Our GMine system addresses both these issues, by using summarization and multi-resolution. GMine offers multi-resolution graph exploration by partitioning a given graph into a hierarchy of communities-within-communities and storing it into a novel R-tree-like structure which we name G-Tree. GMine offers summarization by implementing an innovative subgraph extraction algorithm and then visualizing its output. 1.
InteMon Intelligent System Monitoring on Large Clusters.
InteMon is a prototype monitoring and mining system for large clusters. Currently, it monitors over 100 hosts of a prototype data center at CMU. It uses the SNMP protocol and it stores the monitoring data in an mySQL database. Then, it allows for visualization of the time-series data using a JSP web-based frontend interface for users. What sets it apart from other cluster monitoring systems is its ability to automatically analyze the monitoring data in real time and alert the users for potential anomalies. It uses state of the art stream mining methods, it has a sophisticated definition of anomalies (broken correlations among input streams), and it can also pinpoint the reason of the anomaly. InteMon has a user-friendly GUI, it allows the users to perform interactive mining tasks, and it is fully operational. 1.
Graph mining Laws%2C generators%2C and algorithms.
How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: &#034;How can we generate synthetic but realistic graphs?&#034; To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.
Spatial Query Estimation without the Local Uniformity Assumption.

Efficient Discovery of Unusual Patterns in Time Series .

InteMon continuous mining of sensor data in large%2Dscale self%2Dinfrastructures.
Modern data centers have a large number of components that must be monitored, including servers, switches/routers, and environmental control systems. This paper describes InteMon, a prototype monitoring and mining system for data centers. It uses the SNMP protocol to monitor a new data center at Carnegie Mellon. It stores the monitoring data in a MySQL database, allowing visualization of the time-series data using a JSP web-based frontend interface for system administrators. What sets InteMon apart from other cluster monitoring systems is its ability to automatically analyze correlations in the monitoring data in real time and alert administrators of potential anomalies. It uses efficient, state of the art stream mining methods to report broken correlations among input streams. It also uses these methods to intelligently compress historical data and avoid the need for administrators to configure threshold-based monitoring bands.
On Multidimensional Data and Modern Disks.
With the deeply-ingrained notion that disks can efficiently access only one dimensional data, current approaches for mapping multidimensional data to disk blocks either allow efficient accesses in only one dimension, trading off the efficiency of accesses in other dimensions, or equally penalize access to all dimensions. Yet, existing technology and functions readily available inside disk firmware can identify non-contiguous logical blocks that preserve spatial locality of multidimensional datasets. These blocks, which span on the order of a hundred adjacent tracks, can be accessed with minimal positioning cost. This paper details these technologies, analyzes their trends, and shows how they can be exposed to applications while maintaining existing abstractions. The described approach can achieve the best possible access efficiency afforded by the disk technologies: sequential access along primary dimension and access with minimal positioning cost for all other dimensions. Experimental evaluation of a prototype implementation demonstrates a reduction of overall I/O time for multidimensional data queries between 30 % and 50 % when compared to existing approaches. 1
Online Latent Variable Detection in Sensor Networks.

AutoLag Automatic Discovery of Lag Correlations in Stream Data.
Data streams appear in multiple settings, such as environmental, medical and socioeconomic systems. There are many, fascinating research problems in such settings, like clustering [1], summarization [3], and forecasting [2].
A Multiresolution Symbolic Representation of Time Series.
Efficiently and accurately searching for similarities among time series and discovering interesting patterns is an important and non-trivial problem. In this paper, we introduce a new representation of time series, the Multiresolution Vector Quantized (MVQ) approximation, along with a new distance function. The novelty of MVQ is that it keeps both local and global information about the original time series in a hierarchical mechanism, processing the original time series at multiple resolutions. Moreover, the proposed representation is symbolic employing key subsequences and potentially allows the application of text-based retrieval techniques into the similarity analysis of time series. The proposed method is fast and scales linearly with the size of database and the dimensionality. Contrary to the vast majority in the literature that uses the Euclidean distance, MVQ uses a multi-resolution/hierarchical distance function. We performed experiments with real and synthetic data. The proposed distance function consistently outperforms all the major competitors (Euclidean, Dynamic Time Warping, Piecewise Aggregate Approximation) achieving up to 20 % better precision/recall and clustering accuracy on the tested datasets. 1.
Parameter%2DFree Spatial Data Mining Using MDL.
Consider spatial data consisting of a set of binary features taking values over a collection of spatial extents (grid cells). We propose a method that simultaneously finds spatial correlation and feature co-occurrence patterns, without any parameters. In particular, we employ the Minimum Description Length (MDL) principle coupled with a natural way of compressing regions. This defines what “good” means: a feature co-occurrence pattern is good, if it helps us better compress the set of locations for these features. Conversely, a spatial correlation is good, if it helps us better compress the set of features in the corresponding region. Our approach is scalable for large datasets (both number of locations and of features). We evaluate our method on both real and synthetic datasets. 1
Neighborhood Formation and Anomaly Detection in Bipartite Graphs.
Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (Neighborhood formation), and 2) finding abnormal nodes (Anomaly detection). And we propose algorithms to compute the neighborhood for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify abnormal nodes, using neighborhood information. We evaluate the quality of neighborhoods based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets. 1
ViVo Visual Vocabulary Construction for Mining Biomedical Images.
Given a large collection of medical images of several conditions and treatments, how can we succinctly describe the characteristics of each setting? For example, given a large collection of retinal images from several different experimental conditions (normal, detached, reattached, etc.), how can data mining help biologists focus on important regions in the images or on the differences between different experimental conditions? If the images were text documents, we could find the main terms and concepts for each condition by existing IR methods (e.g., tf/idf and LSI). We propose something analogous, but for the much more challenging case of an image collection: We propose to automatically develop a visual vocabulary by breaking images into n n tiles and deriving key tiles (“ViVos”) for each image and condition. We experiment with numerous domain-independent ways of extracting features from tiles (color histograms, textures, etc.), and several ways of choosing characteristic tiles (PCA, ICA). We perform experiments on two disparate biomedical datasets. The quantitative measure of success is classification accuracy: Our “ViVos ” achieve high classification accuracy (up to 83 % for a nine-class problem on feline retinal images). More importantly, qualitatively, our “ViVos ” do an excellent job as “visual vocabulary terms”: they have biological meaning, as corroborated by domain experts; they help spot characteristic regions of images, exactly like text vocabulary terms do for documents; and they highlight the differences between pairs of images. 1
Example%2DBased Robust Outlier Detection in High Dimensional Datasets.
Detecting outliers is an important problem. Most of its applications typically possess high dimensional datasets. In high dimensional space, the data becomes sparse which implies that every object can be regarded as an outlier from the point of view of similarity. Furthermore, a fundamental issue is that the notion of which objects are outliers typically varies between users, problem domains or, even, datasets. In this paper, we present a novel robust solution which detects high dimensional outliers based on user examples and tolerates incorrect inputs. It studies the behavior of projections of such a few examples, to discover further objects that are outstanding in the projection where many examples are outlying. Our experiments on both real and synthetic datasets demonstrate the ability of the proposed method to detect outliers corresponding to the user examples. 1
Graphs over time densification laws
How do real graphs evolve over time? What are &#034;normal&#034; growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study
Realistic
A vast body of theoretical research has focused either on overly simplistic models of parallel  computation, notably the PRAM, or overly specific models that have few representatives in  the real world. Both kinds of models encourage exploitation of formal loopholes, rather than  rewarding development of techniques that yield performance across a range of current and  future parallel machines. This paper offers a new parallel machine model, called LogP, that  reflects the critical technology trends underlying parallel computers. It is intended to serve  as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine  designers. Such a model must strike a balance between detail and simplicity in order to reveal  important bottlenecks without making analysis of interesting problems intractable. The model  is based on four parameters that specify abstractly the computing bandwidth, the communication  bandwidth, the communication delay, and the efficiency of coupling communication  and computation. Portable parallel algorithms typically adapt to the machine configuration, in  terms of these parameters. The utility of the model is demonstrated through examples that are  implemented on the CM-5.
FTW fast similarity search under the time warping distance.

Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
BRAID Stream Mining through Group Lag Correlations.

Research issues in protein location image databases.

Streaming Pattern Discovery in Multiple Time%2DSeries.
In this paper, we introduce SPIRIT (Streaming  Pattern dIscoveRy in multIple Timeseries)  . Given n numerical data streams, all  of whose values we observe at each time tick  t, SPIRIT can incrementally find correlations  and hidden variables, which summarise the  key trends in the entire stream collection.
A Comparative Study of Feature Vector%2DBased Topic Detection Schemes A Comparative Study of Feature Vector%2DBased Topic Detection Schemes.

Editorial TKDE Topic Area Revisions.

Fast estimation of fractal dimension and correlation integral on stream data.
Given a cloud of N points in an E-dimensional space, we often need to estimate the intrinsic dimensionality D of this cloud. For example, a set of points in 3-dimensional space all following along a straight line has intrinsic (or fractal) dimensionality D=1. Non-integer fractal dimensionality appears pervasively in nature. In this paper we give a very fast method to estimate the fractal dimensionality of the points in a data stream. Algorithms to estimate the fractal dimension exist, from the straightforward quadratic algorithm, to the faster O(NlogN) or even O(N) algorithms that use the so-called box-counting method. However, these algorithms require Ω(N) space, and hence are ill-suited to semi-infinite streams of data. In this paper we propose an algorithm, based on a “tug-of-war ” idea, which computes the fractal dimension in a single pass over the dataset using only constant memory. Experimental results on synthetic and real world data sets demonstrate the effectiveness of our algorithm. Categories and Subject Descriptors G.1.2 [Numerical Analysis]: Approximation – wavelets and fractals, linear approximation, special function approximations;
Relevance search and anomaly detection in bipartite graphs.
Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) finding nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets. 1.
Relation between Fractal Dimension and Performance of Vector Quantization.

Segmenting Motion Capture Data into Distinct Behaviors.
Much of the motion capture data used in animations, commercials, and video games is carefully segmented into distinct motions either at the time of capture or by hand after the capture session. As we move toward collecting more and longer motion sequences, however, automatic segmentation techniques will become important for processing the results in a reasonable time frame.
Approximate Temporal Aggregation.
Temporal aggregate queries retrieve summarized information about records with time-evolving attributes. Existing approaches have at least one of the following shortcomings: (i) they incur large space requirements, (ii) they have high processing cost and (iii) they are based on complex structures, which are not available in commercial systems. In this paper we solve these problems by approximation techniques with bounded error. We propose two methods: the first one is based on multiversion B-trees and has logarithmic worst-case query cost, while the second technique uses off-the-shelf B- and Rtrees, and achieves the same performance in the expected case. We experimentally demonstrate that the proposed methods consume an order of magnitude less space than their competitors and are significantly faster, even for cases that the permissible error bound is very small.
MMSS Multi%2DModal Story%2DOriented Video Summarization.
We propose multi-modal story-oriented video summarization (MMSS) which, unlike previous works that use fine-tuned, domain-specific heuristics, provides a domainindependent, graph-based framework. MMSS uncovers correlation between information of different modalities which gives meaningful story-oriented news video summaries. MMSS can also be applied for video retrieval, giving performance that matches the best traditional retrieval techniques (OKAPI and LSI), with no fine-tuned heuristics such as tf/idf. 1. Introduction and
Automatic image captioning.
In this paper, we examine the problem of automatic image captioning. Given a training set of captioned images, we want to discover correlations between image features and keywords, so that we can automatically find good keywords for a new image. We experiment thoroughly with multiple design alternatives on large datasets of various content styles, and our proposed methods achieve up to a 45% relative improvement on captioning accuracy over the state of the art.
Fast discovery of connection subgraphs.

Recovering latent time%2Dseries from their observed sums network tomography with particle filters.
Hidden variables, evolving over time, appear in multiple settings, where it is valuable to recover them, typically from observed sums. Our driving application is ’network tomography’, where we need to estimate the origin-destination (OD) traffic flows to determine, e.g., who is communicating with whom in a local area network. This information allows network engineers and managers to solve problems in design, routing, configuration debugging, monitoring and pricing. Unfortunately the direct measurement of the OD traffic is usually difficult, or even impossible; instead, we can easily measure the loads on every link, that is, sums of desirable OD flows. In this paper we propose i-FILTER, a method to solve this problem, which improves the state-of-the-art by (a) introducing explicit time dependence, and by (b) using realistic, non-Gaussian marginals in the statistical models for the traffic flows, as never attempted before. We give experiments on real data, where i-FILTER scales linearly with new observations and out-performs the best existing solutions, in a wide variety of settings. Specifically, on real network traffic measured at CMU, and at AT&amp;T, i-FILTER reduced the estimation errors between 15 % and 46 % in all cases.
Automatic multimedia cross%2Dmodal correlation discovery.
Categories and Subject
Fully automatic cross%2Dassociations.
Large, sparse binary matrices arise in numerous data mining applications, such as the analysis of market baskets, web graphs, social networks, co-citations, as well as information retrieval, collaborative filtering, sparse matrix reordering, etc. Virtually all the popular methods for analysis of such matrices—e.g., k-means clustering, METIS graph partitioning, SVD/PCA and frequent itemset mining—require the user to specify various parameters, such as the number of clusters, number of principal components, number of partitions, and “support. ” Choosing suitable values for such parameters is a challenging problem. Cross-association is a joint decomposition of a binary matrix into disjoint row and column groups such that the rectangular intersections of groups are homogeneous. Starting from first principles, we furnish a clear, informationtheoretic criterion to choose a good cross-association as well as its parameters, namely, the number of row and column groups. We provide scalable algorithms to approach the optimal. Our algorithm is parameter-free, and requires no user intervention. In practice it scales linearly with the problem size, and is thus applicable to very large matrices. Finally, we present experiments on multiple synthetic and real-life datasets, where our method gives high-quality, intuitive results. ∗ This material is based upon work supported by the National
Storage Device Performance Prediction with CART Models.
Storage device performance prediction is a key element of self-managed storage systems and application planning tasks, such as data assignment. This work explores the application of a machine learning tool, CART models, to storage device modeling. Our approach predicts a device&#039;s performance as a function of input workloads, requiring no knowledge of the device internals. We propose two uses of CART models: one that predicts per-request response times (and then derives aggregate values) and one that predicts aggregate values directly from workload characteristics. After being trained on our experimental platforms, both provide accurate black-box models across a range of test traces from real environments. Experiments show that these models predict the average and 90th percentile response time with an relative error as low as 16%, when the training workloads are similar to the testing workloads, and interpolate well across different workloads.
GCap Graph%2DBased Automatic Image Captioning.
Abstract Given an image, how do we automatically assign keywordsto it? In this paper, we propose a novel, graph-based approach (GCap) which outperforms previously reportedmethods for automatic image captioning. Moreover, it is fast and scales well, with its training and testing time lin-ear to the data set size. We report auto-captioning experiments on the &amp;quot;standard &amp;quot; Corel image database of 680MBytes, where GCap outperforms recent, successful autocaptioning methods by up to 10 percentage points in cap-tioning accuracy (50 % relative improvement). 1. Introduction and related work Given a huge image database, how do we assign content-descriptive keywords to each image, automatically? In this
OBE Outlier by Example.
Abstract. Outlier detection in large datasets is an important problem. There are several recent approaches that employ very reasonable definitions of an outlier. However, a fundamental issue is that the notion of which objects are outliers typically varies between users or, even, datasets. In this paper, we present a novel solution to this problem, by bringing users into the loop. Our OBE (Outlier By Example) system is, to the best of our knowledge, the first that allows users to give some examples of what they consider as outliers. Then, it can directly incorporate a small number of such examples to successfully discover the hidden concept and spot further objects that exhibit the same “outlier-ness ” as the examples. We describe the key design decisions and algorithms in building such a system and demonstrate on both real and synthetic datasets that OBE can indeed discover outliers that match the users ’ intentions. 1
AutoSplit Fast and Scalable Discovery of Hidden Variables in Stream and Multimedia Databases.

R%2DMAT A Recursive Model for Graph Mining.
How does a ‘normal ’ computer (or social) network look like? How can we spot ‘abnormal ’ sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”). The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such “laws ” and, more importantly, we propose a simple, parsimonious model, the “recursive matrix ” (R-MAT) model, which can quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. Contrary to existing generators, our model can trivially generate weighted, directed and bipartite graphs; it subsumes the celebrated Erdős-Rényi model as a special case; it can match the power law behaviors, as well as the deviations from them (like the “winner does not take it all ” model of Pennock et al. [20]). We present results on multiple, large real graphs, where we show that our parameter fitting algorithm (AutoMAT-fast) fits them very well. 1
Automated Assistance for Eliciting User Expectations.
People often use software for mundane tasks and expect it to be dependable enough for their needs. Unfortunately, the incomplete and imprecise specifications of such everyday software inhibit many dependability enhancement techniques because these require a model of proper behavior for failure detection. We offer a user-centered approach for creating a model of proper behavior. This approach is based on satisfying the user expectations---software behavior the user relies on---rather than demanding perfect specifications. It utilizes data mining through a novel template mechanism, to help users make their expectations precise. The resulting precise expectations can then serve as proxies for missing specifications in detecting unexpected data behavior. We concentrate on data feeds: continuous streams of data, a challenging example of everyday software. Using our method on a real world data feed, it took just hours to detect problems that had taken the data providers months to detect independently. These problems surprised even our user---a domain expert that had previously analyzed the same data feed. Systematic analysis further supports the usefulness of our method.
Storage device performance prediction with CART models.
Storage device performance prediction is a key element of self-managed storage systems and application planning tasks, such as data assignment. This work explores the application of a machine learning tool, CART models, to storage device modeling. Our approach predicts a device&#039;s performance as a function of input workloads, requiring no knowledge of the device internals. We propose two uses of CART models: one that predicts per-request response times (and then derives aggregate values) and one that predicts aggregate values directly from workload characteristics. After being trained on our experimental platforms, both provide accurate black-box models across a range of test traces from real environments. Experiments show that these models predict the average and 90th percentile response time with an relative error as low as 16%, when the training workloads are similar to the testing workloads, and interpolate well across different workloads.
Prediction and Indexing of Moving Objects with Unknown Motion Patterns.
Existing methods for prediction in spatio-temporal databases assume that objects move according to linear functions. This severely limits their applicability, since in practice movement is more complex, and individual objects may follow drastically different motion patterns. In order to overcome these problems, we first introduce a general framework for monitoring and indexing moving objects, where (i) each object computes individually the function that accurately captures its movement and (ii) a server indexes the object locations at a coarse level and processes queries using a filter-refinement mechanism. Our second contribution is a novel recursive motion function that supports a broad class of non-linear motion patterns. The function does not presume any a-priori movement but can postulate the particular motion of each object by examining its locations at recent timestamps. Finally, we propose an efficient indexing scheme that facilitates the processing of predictive queries without false misses. 1.
Indexing and Mining Streams.

Auditing Compliance with a Hippocratic Database.
We introduce an auditing framework for determining whether a database system is adhering to its data disclosure policies. Users formulate audit expressions to specify the (sensitive) data subject to disclosure review. An audit component accepts audit expressions and returns all queries (deemed “suspicious”) that accessed the specified data during their execution. The overhead of our approach on query processing is small, involving primarily the logging of each query string along with other minor annotations. Database triggers are used to capture updates in a backlog database. At the time of audit, a static analysis phase selects a subset of logged queries for further analysis. These queries are combined and transformed into an SQL audit query, which when run against the backlog database, identifies the suspicious queries efficiently and precisely. We describe the algorithms and data structures used in a DB2-based implementation of this framework. Experimental results reinforce our design choices and show the practicality of the approach. 1
Fractal dimension and vector quantization.
Krishna Kumaraswamy  Center for Automated Learning and Discovery, Carnegie Mellon University  skkumar@cs.cmu.edu  Vasileios Megalooikonomou  Department of Computer and Information  Sciences,  Temple University  vasilis@cis.temple.edu  ABSTRACT  Is there a way to determine the performance of a Vector Quantization method? Is there a fast method for determining the performance of a Vector Quantization method? In this paper, we show the relationship between the concepts of Vector Quantization and intrinsic &#034;Fractal&#034; Dimension. We derive a formula predicting the error rate of a Vector Quantization method, given the fractal dimension of the data set. We show that our result is true on synthetic as well as on real data sets. Also, we discuss how we can use our result for better, faster use in several data mining tasks.
Adaptive%2C unsupervised stream mining.

Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
The problem of identifying approximately duplicate records in databases is an essential step for data cleaning and data integration processes. Most existing approaches have relied on generic or manually tuned distance metrics for estimating the similarity of potential duplicates. In this paper, we present a framework for improving duplicate detection using trainable measures of textual similarity. We propose to employ learnable text distance functions for each database field, and show that such measures are capable of adapting to the specific notion of similarity that is appropriate for the field&#039;s domain. We present two learnable text similarity measures suitable for this task: an extended variant of learnable string edit distance, and a novel vector-space based measure that employs a Support Vector Machine (SVM) for training. Experimental results on a range of datasets show that our framework can improve duplicate detection accuracy over traditional techniques.
The power%2Dmethod a comprehensive estimation technique for multi%2Ddimensional queries.
Existing estimation approaches for multi-dimensional databases often rely on the assumption that data distribution in a small region is uniform, which seldom holds in practice. Moreover, their applicability is limited to specific estimation tasks under certain distance metric. This paper develops the Power-method, a comprehensive technique applicable to a wide range of query optimization problems under various metrics. The Powermethod eliminates the local uniformity assumption and is accurate even in scenarios where existing approaches completely fail. Furthermore, it performs estimation by evaluating only one simple formula with minimal computational overhead. Extensive experiments confirm that the Powermethod outperforms previous techniques in terms of accuracy and applicability to various optimization scenarios. 1.

Next Generation Data Mining Tools Power Laws and Self%2Dsimilarity for Graphs

LOCI Fast Outlier Detection Using the Local Correlation Integral.
Outlier detection is an integral part of data mining and has attracted much attention recently [8, 15, 19]. In this paper, we propose a new method for evaluating outlierness, which we call the Local Correlation Integral (LOCI). As with the best previous methods, LOCI is highly effective for detecting outliers and groups of outliers (a.k.a. microclusters). In addition, it offers the following advantages and novelties: (a) It provides an automatic, data-dictated cutoff to determine whether a point is an outlier—in contrast, previous methods force users to pick cut-offs, without any hints as to what cut-off value is best for a given dataset. (b) It can provide a LOCI plot for each point; this plot summarizes a wealth of information about the data in the vicinity of the point, determining clusters, micro-clusters, their diameters and their inter-cluster distances. None of the existing outlier-detection methods can match this feature, because they output only a single number for each point: its outlier-ness score. (c) Our LOCI method can be computed as quickly as the best previous methods. (d) Moreover, LOCI leads to a practically linear approximate method, aLOCI (for approximate LOCI), which provides fast highly-accurate outlier detection. To the best of our knowledge, this is the first work to use approximate computations to speed up outlier detection.
Electricity Based External Similarity of Categorical Attributes.
Abstract. Similarity or distance measures are fundamental and critical properties for data mining tools. Categorical attributes abound in databases. The Car Make, Gender, Occupation, etc. fields in a automobile insurance database are very informative. Sadly, categorical data is not easily amenable to similarity computations. A domain expert might manually specify some or all of the similarity relationships, but this is error-prone and not feasible for attributes with large domains, nor is it useful for cross-attribute similarities, such as between Gender and Occupation. External similarity functions define a similarity between, say, Car Makes by looking at how they co-occur with the other categorical attributes. We exploit a rich duality between random walks on graphs and electrical circuits to develop REP, an external similarity function. REP is theoretically grounded while the only prior work was ad-hoc. The usefulness of REP is shown in two experiments. First, we cluster categorical attribute values showing improved inferred relationships. Second, we use REP effectively as a nearest neighbour classifier. 1
Next Generation Data Mining Tools Power Laws and Self%2Dsimilarity for Graphs

Epidemic Spreading in Real Networks An Eigenvalue Viewpoint.
Abstract How will a virus propagate in a real network?Does an epidemic threshold exist for a finite powerlaw graph, or any finite graph? How long does ittake to disinfect a network given particular values of infection rate and virus death rate? We answer the first question by providing equa-tions that accurately model virus propagation in any network including real and synthesized networkgraphs. We propose a general epidemic threshold condition that applies to arbitrary graphs: weprove that, under reasonable approximations, the epidemic threshold for a network is closely relatedto the largest eigenvalue of its adjacency matrix. Finally, for the last question, we show that infec-tions tend to zero exponentially below the epidemic threshold. We show that our epidemic threshold modelsubsumes many known thresholds for special-case graphs (e.g., Erd&amp;quot;os-R&#039;enyi, BA power-law, homoge-neous); we show that the threshold tends to zero for infinite power-law graphs. Finally, we illustrate thepredictive power of our model with extensive experiments on real and synthesized graphs. We show thatour threshold condition holds for arbitrary graphs.
Cross%2DOutlier Detection.
Abstract. The problem of outlier detection has been studied in the context of several domains and has received attention from the database research community. To the best of our knowledge, work up to date focuses exclusively on the problem as follows [1]: “given a single set of observations in some space, find those that deviate so as to arouse suspicion that they were generated by a different mechanism.” However, in several domains, we have more than one set of observations (or, equivalently, as single set with class labels assigned to each observation). For example, in astronomical data, labels may involve types of galaxies (e.g., spiral galaxies with abnormal concentration of elliptical galaxies in their neighborhood; in biodiversity data, labels may involve different population types, e.g., patches of different species populations, food types, diseases, etc). A single observation may look normal both within its own class, as well as within the entire set of observations. However, when examined with respect to other classes, it may still arouse suspicions. In this paper we consider the problem “given a set of observations with class labels, find those that arouse suspicions, taking into account the class labels. ” This variant has significant practical importance. Many of the existing outlier detection approaches cannot be extended to this case. We present one practical approach for dealing with this problem and demonstrate its performance on real and synthetic datasets. 1
Adaptive%2C Hands%2DOff Stream Mining.
Sensor devices and embedded processors are becoming ubiquitous, especially in measurement and monitoring applications. Automatic discovery of patterns and trends in the large volumes of such data is of paramount importance. The combination of relatively limited resources (CPU, memory and/or communication bandwidth and power) poses some interesting challenges. We need both powerful and concise “languages ” to represent the important features of the data, which can (a) adapt and handle arbitrary periodic components, including bursts, and (b) require little memory and a single pass over the data. This allows sensors to automatically (a) discover interesting patterns and trends in the data, and (b) perform outlier detection to alert users. We need a way so that a sensor can discover something like “the hourly phone call volume so far follows a daily and a weekly periodicity, with bursts roughly every year, ” which a human might recognize as, e.g., the Mother’s day surge. When possible and if desired, the user can then issue explicit queries to further investigate the reported patterns. In this work we propose AWSOM (Arbitrary Window Stream mOdeling Method), which allows sensors operating in remote or hostile environments to discover patterns efficiently and
Power laws and the AS%2Dlevel internet topology.
In this paper, we study and characterize the topology of the Internet at the Autonomous System level. First, we show that the topology can be described efficiently with power-laws. The elegance and simplicity of the powerlaws provide a novel perspective into the seemingly uncontrolled Internet structure. Second, we show that power-laws appear consistently over the last 5 years. We also observe that the power-laws hold even in the most recent and more complete topology [10] with correlation coefficient above 99% for the degree power-law. In addition, we study the evolution of the power-law exponents over the 5 year interval and observe a variation for the degree based power-law of less than 10%. Third, we provide relationships between the exponents and other topological metrics.
An environmental sensor network to determine drinking water quality and security.

F4 large%2Dscale automated forecasting using fractals.
Forecasting has attracted a lot of research interest, with very successful methods for periodic time series. Here, we propose a fast, automated method to do non-linear forecasting, for both periodic as well as chaotic time series. We use the technique of delay coordinate embedding, which needs several parameters; our contribution is the automated way of setting these parameters, using the concept of ‘intrinsic dimensionality’. Our operational system has fast and scalable algorithms for preprocessing and, using R-trees, also has fast methods for forecasting. The result of this work is a blackbox which, given a time series as input, finds the best parameter settings, and generates a prediction system. Tests on real and synthetic data show that our system achieves low error, while it can handle arbitrarily large datasets. Categories and Subject Descriptors H.2.8 [Database Applications]: Data Mining—time series forecasting

%22GeoPlot%22 spatial data mining on video libraries.

Future directions in data mining streams

Indexing Values in Continuous Field Databases.

VideoCube A Novel Tool for Video Mining and Classification.
VideoCube: a novel tool for video mining and classification
Data Mining Meets Performance Evaluation Fast Algorithms for Modeling Bursty Traffic.
Network, web, and disk I/O traffic are usually bursty, self-similar [9, 3, 5, 6] and therefore can not be modeled adequately with Poisson arrivals[9]. However, we do want to model these types of traffic and to generate realistic traces, because of obvious applications for disk scheduling, network management, web server design. Previous models (like fractional Brownian motion, ARFIMA etc) tried to capture the ‘burstiness’. However the proposed models either require too many parameters to fit and/or require prohibitively large (quadratic) time to generate large traces. We propose a simple, parsimonious method, the b-model, which solves both problems: It requires just one parameter (b), and it can easily generate large traces. In addition, it has many more attractive properties: (a) With our proposed estimation algorithm, it requires just a single pass over the actual trace to estimate b. For example, a one-day-long disk trace in milliseconds contains about 86Mb data points and requires about 3 minutes for model fitting and 5 minutes for generation. (b) The resulting synthetic traces are very realistic: our experiments on real disk and web traces show that our synthetic traces match the real ones very well in terms of queuing behavior.
Data Visualization in RDBMS.

Making every bit count fast nonlinear axis scaling.

ANF a fast and scalable tool for data mining in massive graphs.
Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene sequences, city streets, social networks and academic citations. Any kind of relationship, such as actors appearing in movies, can be represented as a graph. This work presents a data mining tool, called ANF, that can quickly answer a number of interesting questions on graph-represented data, such as the following. How robust is the Internet to failures? What are the most influential database papers? Are there gender differences in movie appearance patterns? At its core, ANF is based on a fast and memory-efficient approach for approximating the complete &#034;neighbourhood function&#034; for a graph. For the Internet graph (268K nodes), ANF&#039;s highly-accurate approximation is more than 700 times faster than the exact computation. This reduces the running time from nearly a day to a matter of a minute or two, allowing users to perform ad hoc drill-down tasks and to repeatedly answer questions about changing data sources. To enable this drill-down, ANF employs new techniques for approximating neighbourhood-type functions for graphs with distinguished nodes and/or edges. When compared to the best existing approximation, ANF&#039;s approach is both faster and more accurate, given the same resources. Additionally, unlike previous approaches, ANF scales gracefully to handle disk resident graphs. Finally, we present some of our results from mining large graphs using ANF.
Sensor Data Mining Similarity Search and Pattern Analysis.

Data%2Ddriven evolution of data mining algorithms.

Fast Indexing and Visualization of Metric Data Sets using Slim%2DTrees.

ImageMap An Image Indexing Method Based on Spatial Similarity.
We introduce ImageMap, as a method for indexing and similarity searching in Image DataBases (IDBs). ImageMap answers &#034;queries by example&#034;, involving any number of objects or regions and taking into account their inter-relationships. We adopt the most general image content representation, that is Attributed Relational Graphs (ARGs), in conjunction with the well-accepted ARG editing distance  on ARGs. We tested ImageMap on real and realistic medical images. Our method not only provides for visualization of the dataset, clustering and data-mining, but it also achieves up to 1,000-fold speed-up in search over sequential scanning, with zero or very few false dismissals.
Fundamentals of Scheduling and Performance of Video Tape Libraries.
Robotic tape libraries are popular for applications with very high storage requirements, such as video servers. Here, we study the throughput of a tape library system, we design a new scheduling algorithm, the so-called Relief, and compare it against some older/straightforward ones, like FCFS, Maximum Queue Length (MQL) and an unfair one (Bypass), roughly equivalent to Shortest Job First. The proposed algorithm incorporates an aging mechanism in order to attain fairness and we prove that, under certain assumptions, it minimizes the average start-up latency. Extensive simulation experiments show that Relief outperforms its competitors (fair and unfair alike), with up to 203 % improvement in throughput, for the same rejection ratio. 1
Capturing the spatio%2Dtemporal behavior of real traffic data.
Traffic, like disk and memory accesses, typically exhibits burstiness, temporal locality and  spatial locality. There is much recent ground-breaking work on temporal modeling (self-similarity  etc), on disk and web traffic, with several statistical models that generate realistic series of time-  stamps. However, no work generates realistic traces for both time and location (eg., block-id).
KDD%2D2002 Workshop Report Fractals and Self%2Dsimilarity in Data Mining Issues and Approaches.

Similarity Search without Tears The OMNI Family of All%2Dpurpose Access Methods.

VideoGraph a new tool for video mining and classification.
This paper introduces VideoGraph, a new tool for video mining and visualizing the structure of the plot of a video sequence. The main idea is to \stitch&#034; together similar scenes which are apart in time. We give a fast algorithm to do stitching and we show case studies, where our approach (a) gives good features for classication (91% accuracy), and (b) results in VideoGraphs which reveal the logical structure of the plot of the video clips.
The %22DGX%22 distribution for mining massive%2C skewed data.
Skewed distributions appear very often in practice. Unfortunately, the traditional Zipf distribution often fails to model them well. In this paper, we propose a new probability distribution, the Discrete Gaussian Exponential (DGX), to achieve excellent fits in a wide variety of settings; our new distribution includes the Zipf distribution as a special case. We present a statistically sound method for estimating the DGX parameters based on maximum likelihood estimation (MLE). We applied DGX to a wide variety of real world data sets, such as sales data from a large retailer chain, usage data from AT&amp;T, and Internet clickstream data; in all cases, DGX fits these distributions very well, with almost a 99 % correlation coefficient in quantile-quantile plots. Our algorithm also scales very well because it requires only a single pass over the data. Finally, we illustrate the power of DGX as a new tool for data mining tasks, such as outlier detection. Keywords DGX, Zipf’s law, rank-frequency plot, frequency-count plot, maximum likelihood estimation, lognormal distribution, outlier detection
Tri%2Dplots scalable tools for multidimensional data mining.
We focus on the problem of finding patterns across two large, multidimensional datasets. For example, given feature vectors of healthy and of non-healthy patients, we want to answer the following questions: Are the two clouds of points separable? What is the smallest/largest pair-wise distance across the two datasets? Which of the two clouds does a new point (feature vector) come from? We propose a new tool, the tri-plot, and its generalization, the pq-plot, which help us answer the above questions. We provide a set of rules on how to interpret a tri-plot, and we apply these rules on synthetic and real datasets. We also show how to use our tool for classification, when traditional methods (nearest neighbor, classification trees) may fail. 1 
NetCube A Scalable Tool for Fast Data Mining and Compression.
We propose an novel method of computing and storing DataCubes. Our idea is to use Bayesian Networks, which can generate approximate counts for any query combination of attribute values and &#034;don&#039;t cares.&#034; A Bayesian network represents the underlying joint probability distribution of the data that were used to generate it. By means of such a network the proposed method, NetCube, exploits correlations among attributes. Our proposed preprocessing algorithm scales linearly on the size of the database, and is thus scalable; it is also parallelizable with a straightforward parallel implementation. Moreover, we give an algorithm to estimate counts of arbitrary queries that is fast (constant on the database size). Experimental results show that NetCubes have fast generation and use (a few minutes preprocessing time per 100,000 records and less than a second query time), achieve excellent compression (at least 1800:1 compression ratios on real data) and have low reconstruction error (less than 5% on average). Moreover, our method naturally allows for visualization and data mining, at no extra cost.  Keywords: DataCube approximation, count query, Bayesian network, Bayesian network structure learning, machine learning.  1 The Problem  The problem of computing counts of records with desired characteristics from a database is a very common one in the area of decision support systems and data mining. A typical scenario is as follows: a customer analyst wants to discover groups of customers that exhibit an interesting or unusual behavior that might lead to possibly profitable insights into the company&#039;s customer behavior. In other words, a company wants to be able to model its customer base well, and the better it is able to do that, the more insights it can obtain from the model and m...
Active Disks for Large%2DScale Data Processing.
p, leaving  sufficient area to include a 200-MHz ARM core  or similar embedded microprocessor.  Disk drive and chip manufacturers are already pursuing  this processor-in-ASIC technology. Infineon (formerly  Siemens Microelectronics) markets a chip called  the TriCore that includes a 100-MHz 32-bit microcontroller,  up to 2 Mbytes of on-chip RAM, and customer  -specific logic---such as the disk functions of  Figure 1, upper right---in a .35 micron process. Cirrus  Logic offers an integrated system-on-chip hard disk  drive controller called 3Ci that includes a 25-MHz  ARM core in the first generation, with promise of 200  MHz in the next generation.  Taking a larger system view, Table 1 shows details  of several large database systems that manage transaction  and data mining workloads. These trends and  ratios in CPU versus aggregate processing power have  remained roughly steady since we compiled this data  in 1998 using information from the Transaction  Processing Performance Council, 
Identifying Web Browsing Trends and Patterns.

Multimedia Queries by Example and Relevance Feedback.
We describe the FALCON system for handling multimedia queries with relevance feedback. FALCON distinguishes itself in its ability to handle even disjunctive queries on metric spaces. Our experiments show that it performs well on both real and synthetic data in terms of precision/recall, speed of convergence, individual query speed, and scalability. Moreover, it can easily take advantage of off-the-shelf spatial- and metric- access methods. 1
Analysis of the Clustering Properties of the Hilbert Space%2DFilling Curve.
AbstractÐSeveral schemes for the linear mapping of a multidimensional space have been proposed for various applications, such as access methods for spatio-temporal databases and image compression. In these applications, one of the most desired properties from such linear mappings is clustering, which means the locality between objects in the multidimensional space being preserved in the linear space. It is widely believed that the Hilbert space-filling curve achieves the best clustering [1], [14]. In this paper, we analyze the clustering property of the Hilbert space-filling curve by deriving closed-form formulas for the number of clusters in a given query region of an arbitrary shape (e.g., polygons and polyhedra). Both the asymptotic solution for the general case and the exact solution for a special case generalize previous work [14]. They agree with the empirical results that the number of clusters depends on the hypersurface area of the query region and not on its hypervolume. We also show that the Hilbert curve achieves better clustering than the z curve. From a practical point of view, the formulas given in this paper provide a simple measure that can be used to predict the required disk access behaviors and, hence, the total access time.

On the %27Dimensionality Curse%27 and the %27Self%2DSimilarity Blessing%27.

Accurate Modeling of Region Data.
Spatial data appear in numerous applications, such as GIS [8, 9, 18], multimedia [6] and even traditional databases. Most of the analysis has focused on point data, typically using the uniformity assumption, or, more accurately, a fractal distribution [5]. However, no results exist for non-point spatial data, like 2-d regions (e.g., islands), 3-d volumes (e.g., physical objects in the real world) etc. This is exactly the problem we solve in this paper. Based on experimental evidence that real areas and volumes follow a &#034;power law&#034;, that we named REGAL (REGion Area Law), we show (a) the theoretical implications of our model and its connection with the ubiquitous fractals and (b) the first of its practical uses, namely the selectivity estimation for range queries. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our method is extremely accurate, enjoying a maximum relative error ranging from 1 to 5%, versus 30-70% of a naive model that uses the ...
Slim%2DTrees High Performance Metric Trees Minimizing Overlap Between Nodes.
Abstract. In this paper we present the Slim-tree, a dynamic tree for organizing metric datasets in pages of fixed size. The Slim-tree uses the “fat-factor ” which provides a simple way to quantify the degree of overlap between the nodes in a metric tree. It is well-known that the degree of overlap directly affects the query performance of index structures. There are many suggestions to reduce overlap in multidimensional index structures, but the Slim-tree is the first metric structure explicitly designed to reduce the degree of overlap. Moreover, we present new algorithms for inserting objects and splitting nodes. The new insertion algorithm leads to a tree with high storage utilization and improved query performance, whereas the new split algorithm runs considerably faster than previous ones, generally without sacrificing search performance. Results obtained from experiments with real-world data sets show that the new algorithms of the Slim-tree consistently lead to performance improvements. After
Online Data Mining for Co%2DEvolving Time Sequences.
In many applications, the data of interest comprises multiple sequences that evolve over time. Examples include currency exchange rates, network traffic data. We develop a fast method to analyze such co-evolving time sequences  jointly to allow (a) estimation/forecasting of missing /delayed/future values, (b) quantitative data mining,and (c) outlier detection. Our method, MUSCLES, adapts to changing correlations among time sequences. It can handle indefinitely long sequences efficiently using an incremental algorithm and requires only small amount of storage and less I/O operations. To make it scale for a large number of sequences, we present a variation, the Selective MUSCLES method and propose an efficient algorithm to reduce the problem size. Experiments on real datasets show that MUSCLES outperforms popular competitors in prediction accuracy up to 10 times, and discovers interesting correlations. Moreover, Selective MUSCLES scales up very well for large numbers of sequences, reducing response time up to 110 times over MUSCLES, and sometimes even improves the prediction quality.

Deflating the Dimensionality Curse Using Multiple Fractal Dimensions.
1
Fast Feature Selection Using Fractal Dimension.
Dimensionalitycurse and dimensionality reduction are two issues that have retained high interest for data mining, machine learning, multimedia indexing, and clustering. We present a fast, scalable algorithm to quickly select the most important attributes (dimensions) for a given set of n-dimensional vectors. In contrast to older methods, our method has the following desirable properties: (a) it does not do rotation of attributes, thus leading to easy interpretation of the resulting attributes; (b) it can spot attributes that have nonlinear correlations; (c) it requires a constant number of passes over the dataset; (d) it gives a good estimate on how many attributes we should keep.  The idea is to use the `fractal&#039; dimension of a dataset as a good approximation of its intrinsic dimension, and to drop attributes that do not affect it. We applied our method on real and synthetic datasets, where it gave fast and good results.  1 - Introduction and Motivation  Whenmanaging the increasing vo...
Data Mining on an OLTP System %28Nearly%29 for Free.
This paper proposes a scheme for scheduling disk requests that takes advantage of the ability of high-level functions to operate directly at individual disk drives. We show that such a scheme makes it possible to support a Data Mining workload on an OLTP system almost for free: there is only a small impact on the throughput and response time of the existing workload. Specifically, we show that an OLTP system has the disk resources to consistently provide one third of its sequential bandwidth to a background Data Mining task with close to zero impact on OLTP throughput and response time at high transaction loads. At low transaction loads, we show much lower impact than observed in previous work. This means that a production OLTP system can be used for Data Mining tasks without the expense of a second dedicated system. Our scheme takes advantage of close interaction with the on-disk scheduler by reading blocks for the Data Mining workload as the disk head &#034;passes over&#034; them while satisfy...
Spatial Join Selectivity Using Power Laws.
We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is &#034;find the libraries that are within 10 miles of schools&#034;. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call &#034;pair-count exponent&#034; (PC). We show that this law also holds for self-spatial-joins (&#034;find schools within 5 miles of other schools&#034;) in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy). In addition, we introduce the concept of the Box-Occupancy-Product-Sum (BOPS) plot, and we show that it can compute the pair-count exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the pair-count exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant t...
Density Biased Sampling An Improved Method for Data Mining and Clustering.
Data mining in large data sets often requires a sampling or summarization step to form an in-core representation of the data that can be processed more efficiently. Uniform random sampling is frequently used in practice and also frequently criticized because it will miss small clusters. Many natural phenomena are known to follow Zipf &#039;s distribution and the inability of uniform sampling to find small clusters is of practical concern. Density Biased Sampling is proposed to probabilistically under-sample dense regions and oversample light regions. A weighted sample is used to preserve the densities of the original data. Density biased sampling naturally includes uniform sampling as a special case. A memory efficient algorithm is proposed that approximates density biased sampling using only a single scan of the data. We empirically evaluate density biased sampling using synthetic data sets that exhibit varying cluster size distributions finding up to a factor of six improvement over uniform s...
Searching%2C Data Mining and Visualization of Multimedia Data.

FALCON Feedback Adaptive Loop for Content%2DBased Retrieval.
Several methods currently exist that can  perform relatively simple queries driven  by relevance feedback on large multimedia  databases. However, all these methods work  only for vector spaces; that is, they require  that objects be represented as vectors within  feature spaces. Moreover, their implied query  regions are typically convex. This research paper  explains our solution.  We propose a novel method that is designed  to handle disjunctive queries within metric  spaces. The user provides weights for positive  examples; our system &#034;learns&#034; the implied  concept and returns similar objects.  Our method differs from existing relevancefeedback  methods that base themselves upon  Euclidean or Mahalanobis metrics, as it facilitates  learning even disjunctive, concave models  within vector spaces, as well as arbitrary  metric spaces. In addition, our method is  completely example-driven, and imposes no  requirements upon the user for other aspects  such as feature selection.  Our main...
Fast Time Sequence Indexing for Arbitrary Lp Norms.

Analysis of Range Queries and Self%2DSpatial Join Queries on Real Region Datasets Stored Using an R%2DTree.

Reminiscences on Influential Papers.

Quantifiable Data Mining Using Ratio Rules.
Association Rule Mining algorithms operate on a data matrix (e.g., customers \Theta products) to derive association rules (Agrawal, Imielinski, &amp; Swami, 1993b; Srikant &amp; Agrawal, 1996). We propose a new paradigm, namely, Ratio  Rules, which are quantifiable in that we can measure the &#034;goodness&#034; of a set of discovered rules. We also propose the &#034;guessing error&#034; as a measure of the &#034;goodness&#034;, that is, the root-mean-square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing/hiddenvalues from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can &#034;guess&#034; the amount spent on butter. Thus, unlike association rules, Ratio Rules can perform a variety of important tasks such as forecasting, answering &#034;what-if&#034; scenarios, detecting outliers, and visualizing the data. Moreover, we show that we can compute Ratio Rules in a sing...
SIGMOD 1999
ObjectRank [1] is a system to perform authority-based keyword search on databases, inspired by PageRank [3]. PageRank is an excellent tool to rank the global importance of the pages of the Web, proven by the success of Google 1. However, Google uses
I%2FO Complexity for Range Queries on Region Data Stored Using an R%2Dtree.
In this paper we study the node distribution of an R-tree storing region data, like for instance islands, lakes or human-inhabited areas. We will show that real region datasets are packed in minimum bounding rectangles (MBRs) whose area distribution follows the same power law, named REGAL (REGion Area Law) [12], as that for the regions themselves. Moreover, these MBRs are packed in their turn into MBRs following the same law, and so on iteratively, up to the root of the R-tree. Based on this observation, we are able to accurately estimate the search effort for range queries, the most prominent spatial operation, using a small number of easy-to-retrieve parameters. Experiments on a variety of real datasets (islands, lakes, human-inhabited areas) show that our estimation is accurate, enjoying a maximum geometric average relative error within 30%.
On Power%2Dlaw Relationships of the Internet Topology.
Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher. Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.  1 Introduction  &#034;What does the Internet look like?&#034; &#034;Are there any topological properties that don&#039;t change in time?&#034; &#034;How will it look like a year ...
Automated Learning and Discovery State%2Dof%2Dthe%2DArt and Research Topics in a Rapidly Growing Field.
This report summarizes the CONALD meeting, which took place June 11-13, 1998, at Carnegie Mellon University. CONALD brought together an interdisciplinary group of scientists, concerned with decision making based on data. This report is organized in two parts. The first part (pages 1-6) summarizes the CONALD meeting and highlights its main outcomes, beyond the individual workshop level. The second part (pages 7-30) summarizes the results obtained in the individual workshops, discussing in depth promising research topics. This report is also available through the Web at http://www.cs.cmu.edu/¸conald. CONALD was supported financially by the National Science Foundation under grant number IIS-9813354, which is gratefully acknowledged. Further financial support from CALD&#039;s corporate members is gratefully acknowledged: Caterpillar, Inc., Exxon Paramins, Giant Eagle, Inc., KeyBank, Mellon Bank, Schlumberger Cambridge Research, Siemens Corporate Research, Inc., VSI Satech, and Westinghouse Scie...
Selectivity Estimation of Window Queries.
Despite of the fact that large line segment datasets are appearing more and more frequently in numerous applications involving spatial data, such as GIS [8, 9] multimedia [6] and even traditional databases, most of the analysis for estimating the selectivity of window queries posed on spatial data --the most important parameter for query optimization-- has focused on point or region data only. In this paper we move one significant step forward in line segment datasets theoretical analysis. We discovered that real lines closely follow a distribution law, that we named the SLED law (Segment LEngth Distribution). The SLED law can be used for an accurate estimation of the selectivity of window queries. Experiments on a variety of real line segment datasets (hydrographic systems, roadmaps, railroads, utilities networks) show that our law holds and that our formula is extremely accurate, enjoying a maximum relative error of 4% in estimating the selectivity.    On leave from Dipartimento di M...
Image Indexing and Retrieval Based on Human Perceptual Color Clustering.
We propose a new image retrieval method based on human perceptual clustering of color images. This color clustering produces for each image a small set of representative colors which captures the color properties of the image, and a small set of sizable contiguous regions which captures the spatial/geometrical properties of the image. The proposed method outperforms the traditional histogram and its improved methods not only with its richer image retrieval capabilities which cover a wider spectrum of user requirements, but also with its powerful indexing scheme which is essential to cater for large scale image databases. 1
Efficient Retrieval of Similar Time Sequences Under Time Warping.
Fast similarity searching in large time-sequence databases has attracted a lot of research interest [1, 5, 2, 6, 3, 10]. All of them use the Euclidean distance (L 2 ), or some variation of L p metrics. L p  metrics lead to efficient indexing, thanks to feature extraction (e.g., by keeping the first few DFT coefficients) and subsequent use of fast spatial access methods for the points in feature space. In this work we examine a popular, field-tested dissimilarity function, the &#034;time warping&#034; distance function which permits local accelerations and decelerations in the rate of the signals or sequences. This function is natural and suitable for several applications, like matching of voice, audio and medical signals (e.g., electrocardiograms) However, from the indexing viewpoint it presents two major challenges: (a) it does not lead to any natural &#034;features&#034;, precluding the use of spatial access methods (b) it is quadratic (O(len 1  len 2 )) on the length of the sequences involved. Here we ...
Developing High%2DLevel Representations of Video Clips using VideoTrails.
A high-level representation of a video clip comprising information about its physical and semantic structure is necessary for providing appropriate processing, indexing and retrieval capabilities for video databases. We describe a novel technique which reduces a sequence of MPEG encoded video frames to a trail of points in a low dimensional space. In our earlier work,  1  we presented techniques applicable in 3-D, but in this paper, we describe techniques that can be extended to higher dimensions where improved performance is expected. In the low-dimensional space, we can cluster frames, analyze transitions between clusters and compute properties of the resulting trail. Portions of the trail can be classified as either stationary or transitional, leading to high-level descriptions of the video. Tracking the interaction of clusters over time, we lay the groundwork for the complete analysis and representation of the video&#039;s physical and semantic structure.  Keywords: Video Representation...
MindReader Querying Databases Through Multiple Examples.
Users often can not easily express their queries. For example, in a multimedia/image by content setting, the user might want photographs with sunsets; in current systems, like QBIC, the user has to give a sample query, and to specify the relative importance of color, shape and texture. Even worse, the user might want correlations between attributes, like, for example, in a traditional, medical record database, a medical researcher might want to find &#034;mildly overweight patients&#034;, where the implied query would be &#034;weight/height &amp;asymp; 4 lb/inch&#034;. Our goal is to provide a user-friendly, but theoretically solid method, to handle such queries. We allow the user to give several examples, and, optionally, their &#039;goodness&#039; scores, and we propose a novel method to &#034;guess&#034; which attributes are important, which correlations are important, and with what weight. Our contributions are twofold: (a) we formalize the problem as a minimization problem and show how to solve for the optimal solution, completely av...
Ratio Rules A New Paradigm for Fast%2C Quantifiable Data Mining.
Association Rule Mining algorithms operate on a data matrix (e.g., customers \Theta products) to derive association rules [2, 23]. We propose a new paradigm, namely, Ratio Rules,  which are quantifiable in that we can measure the &#034;goodness&#034; of a set of discovered rules. We propose to use the &#034;guessing error&#034; as a measure of the &#034;goodness&#034;, that is, the rootmean -square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing /hidden values from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can &#034;guess&#034; the amount spent on, say, butter. Thus, we can perform a variety of important tasks such as forecasting, answering &#034;what-if&#034; scenarios, detecting outliers, and visualizing the data. Moreover, we show how to compute Ratio Rules in a single pass over the dataset with small memory requirements (a few small matrices), in co...
Active Storage for Large%2DScale Data Mining and Multimedia.
The increasing performance and decreasing cost of processors and memory are causing system intelligence to move into peripherals from the CPU. Storage system designers are using this trend toward &#034;excess&#034; compute power to perform more complex processing and optimizations inside storage devices. To date, such optimizations have been at relatively low levels of the storage protocol. At the same time, trends in storage density, mechanics, and electronics are eliminating the bottleneck in moving data off the media and putting pressure on interconnects and host processors to move data more efficiently. We propose a system called Active Disks that takes advantage of processing power on individual disk drives to run application-level code. Moving portions of an application &#039;s processing to execute directly at disk drives can dramatically reduce data traffic and take advantage of the storage parallelism already present in large systems today. We discuss several types of applications that would...
Self%2DSpacial Join Selectivity Estimation Using Fractal Concepts.

Designing Access Methods for Bitemporal Databases.

Fast and Effective Retrieval of Medical Tumor Shapes.
Abstract—We investigate the problem of retrieving similar shapes from a large database; in particular, we focus on medical tumor shapes (“Find tumors that are similar to a given pattern.”). We use a natural similarity function for shape-matching, based on concepts from mathematical morphology, and we show how it can be lower-bounded by a set of shape features for safely pruning candidates, thus giving fast and correct output. These features can be organized in a spatial access method, leading to fast indexing for range queries and nearest-neighbor queries. In addition to the lower-bounding, our second contribution is the design of a fast algorithm for nearest-neighbor search, achieving significant speedup while provably guaranteeing correctness. Our experiments demonstrate that roughly 90 percent of the candidates can be pruned using these techniques, resulting in up to 27 times better performance compared to sequential scan. Index Terms—Content-based retrieval, multimedia indexing, mathematical morphology, pattern spectrum.
Overlay Striping and Optimal Parallel I%2FO for Modern Applications.
Disk array systems are rapidly becoming the secondary-storage media of choice for many emerging applications with large storage and high bandwidth requirements. Striping data across the disks of a disk array introduces significant performance benefits mainly because the effective transfer rate of the secondary storage is increased by a factor equal to the stripe width. However, the choice of the optimal stripe width is an open problem: no general formal analysis has been reported and intuition alone fails to provide good guidelines. As a result one may find occasionally contradictory recommendations in the literature. With this work we first contribute an analytical calculation of the optimal stripe width. Second, we recognize that the optimal stripe width is sensitive to the multiprogramming level, which is not known a priori and fluctuates with time. Thus, calculations of the optimal stripe width are, by themselves only, of little practical use. For this reason we propose a novel str...
Advanced Database Systems.
Monet is a customizable database system developed at CWI and University of Amsterdam, intended to be used as the database backend for widely varying application domains. It is designed to get maximum database performance out of today&#039;s workstations and multiprocessor systems. It has already achieved considerable success in supporting a Data Mining application [12, 13], and work is well under way in a project where it is used in a high-end GIS application. Monet is a type- and algebra-extensible database system and employs shared memory parallelism. In this paper, we give the goals and motivation of Monet, and outline its architectural features, including its use of the Decomposed Storage Model (DSM), emphasis on bulk operations, use of main virtual-memory and server customization. As a case example, we discuss some issues on how to build a GIS on top of Monet; amongst others how Monet can handle the very large data volumes involved.   Parts of this work are supported by SION grant no. ...
VideoTrails Representing and Visualizing Structure in Video Sequences.
The problem of determining the physical and semantic structure of an extended video sequence is essential for providing appropriate processing, indexing and retrieval capabilities for video databases. In this paper, we describe a novel technique which reduces a sequence of MPEG encoded video frames to a trail of points in a low dimensional space. In this space, we can cluster frames, analyze transitions between clusters and compute properties of the resulting trail. By classifying portions of the trail as either stationary or transitional, we are able to detect gradual edits between shots. Furthermore, tracking the interaction of clusters over time, we lay the groundwork for the complete analysis and representation of the video&#039;s physical and semantic structure. 1 Introduction  Recent advances in digital storage technology and computer performance has led to the wide spread distribution of video and has promoted video as a valuable information resource. We can now obtain near real-time...
Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences.
Ad hoc querying is difficult on very large datasets, since it is usually not possible to have the entire dataset on disk. While compression can be used to decrease the size of the dataset, compressed data is notoriously difficult to index or access. In this paper we consider a very large dataset comprising multiple distinct time sequences. Each point in the sequence is a numerical value. We show how to compress such a dataset into a format that supports ad hoc querying, provided that a small error can be tolerated when the data is uncompressed. Experiments on large, real world datasets (AT&amp;T customer calling patterns) show that the proposed method achieves an average of less than 5% error in any data value after compressing to a mere 2.5% of the original space (i.e., a 40:1 compression ratio), with these numbers not very sensitive to dataset size. Experiments on aggregate queries achieved a 0.5% reconstruction error with a space requirement under 2%. 1 Introduction The bulk of the data...
Compressed%2DDomain Video Indexing Techniques Using DCT and Motion Vector Information in MPEG Video.
Development of various multimedia applications hinges on the availability of fast and efficient storage, browsing, indexing, and retrieval techniques. Given that video is typically stored efficiently in a compressed format, if we can analyze the compressed representation directly, we can avoid the costly overhead of decompressing and operating at the pixel level. Compressed domain parsing of video has been presented in earlier work where a video clip is divided into shots, subshots, and scenes.  9,11  In this paper, we describe key frame selection, feature extraction, and indexing and retrieval techniques that are directly applicable to MPEG compressed video. We develop a frame-type independent representation of the various types of frames present in an MPEG video in which all frames can be considered equivalent. Features are derived from the available DCT, macroblock, and motion vector information and mapped to a low-dimensional space where they can be accessed with standard database ...
Multimedia Indexing over the Web.
There has been work on database systems that can retrieve multimedia objects by their content. We are extending this work by using the World Wide Web as source and storage for multimedia objects much like current text search engines do for textual information. A system that can access all types of multimedia objects by their content is a formidable task and improvements are constantly being made to indexing techniques. We have taken an important first step in demonstrating the viability of this technique while laying the groundwork for a larger, more capable system. We have implemented a simple indexing scheme while concentrating on building the infrastructure to support this system. Our system can retrieve references to images on the WWW, index those images, and store those images using spatial access methods. We then use query by example to find a set of images on the WWW that resemble our query image. Due to its design, it is easy to include additional context features, to substitut...
Multidimensional Access Methods Trees Have Grown Everywhere.


Recovering Information from Summary Data.
Data is often stored in summarized form, as a histogram of aggregates (COUNTs, SUMs, or AVeraGes) over specified ranges. We study how to estimate the original detail data from the stored summary. We formulate this task as an inverse problem,  specifying a well-defined cost function that has to be optimized under constraints. We show that our formulation includes the uniformity and independence assumptions as a special case, and that it can achieve better reconstruction results if we maximize the smoothness as opposed to the uniformity. In our experiments on real and synthetic datasets, the proposed method almost consistently outperforms its competitor, improving the root-mean-square error by up to 20 per cent for stock price data, and up to 90 per cent for smoother data sets. Finally, we show how to apply this theory to a variety of database problems that involve partial information, such as OLAP, data warehousing and histograms in query optimization.
Indexing of Multimedia Data.

The New Jersey Data Reduction Report.
There is often a need to get quick approximate answers from large databases. This leads to a need for data reduction. There are many di erent approaches to this problem, some of them not traditionally posed as solutions to a data reduction problem. In this paper we describe and evaluate several popular techniques for data reduction.
Analysis of the n%2DDimensional Quadtree Decomposition for Arbitrary Hyperectangles.

Similarity Searching in Medical Image Databases.

Relaxing the Uniformity and Independence Assumptions Using the Concept of Fractal Dimension.


Fast Nearest Neighbor Search in Medical Image Databases.
We examine the problem of finding similar tumor  shapes. Starting from a natural similarity  function (the so-called `max morphological  distance&#039;), we show how to lower-bound it and  how to search for nearest neighbors in large  collections of tumor-like shapes.  Specifically, we use state-of-the-art concepts  from morphology, namely the `pattern spectrum  &#039; of a shape, to map each shape to a point  in n-dimensional space. Following [16, 30], we  organize the n-d points in an R-tree. We show  that the L1 (= max) norm in the n-d space  lower-bounds the actual distance. This guarantees  no false dismissals for range queries. In  addition, we present a nearest neighbor algorithm  that also guarantees no false dismissals.  Finally, we implemented the method and  tested it against a testbed of realistic tumor  shapes, using an established tumor-growth  model of Murray Eden[13]. The experiments  Permission to copy without fee all or part of this material is granted provided that the copies ...
Modeling Skewed Distribution Using Multifractals and the %6080%2D20%27 Law.
law&#039;
Analysis of n%2DDimensional Quadtrees using the Hausdorff Fractal Dimension
There is mounting evidence [Man77, Sch91] that real datasets are statistically self-similar, and thus, `fractal&#039;. This is an important insight since it permits a compact statistical description of spatial datasets; subsequently, as we show, it also forms the basis for the theoretical analysis of spatial access methods, without using the typical, but unrealistic, uniformity assumption. In this paper, we focus on the estimation of the number of quadtree blocks that a real, spatial dataset will require. Using the the well-known Hausdorff fractal dimension, we derive some closed formulas which allow us to predict the number of quadtree blocks, given some few parameters. Using our formulas, it is possible to predict the space overhead and the response time of linear quadtrees/z-ordering [OM88], which are widely used in practice. In order to verify our analytical model, we performed an extensive experimental investigation using several real datasets coming from different domains. In these ex...
Design and Implementation of QBISM%2C a 3D Medical Image Database System.

Experimenting with Pattern%2DMatching Algorithms.

FastMap A Fast Algorithm for Indexing
A very promising idea for fast searching in traditional and multimedia databases is to map objects  into points in k-d space, using k feature-extraction functions, provided by a domain expert [Jag91].  Thus, we can subsequently use highly fine-tuned spatial access methods (SAMs), to answer several  types of queries, including the `Query By Example&#039; type (which translates to a range query); the `all  pairs&#039; query (which translates to a spatial join [BKSS94]); the nearest-neighbor or best-match query,  etc.  However, designing feature extraction functions can be hard. It is relatively easier for a domain  expert to assess the similarity/distance of two objects. Given only the distance information though,  it is not obvious how to map objects into points.  This is exactly the topic of this paper. We describe a fast algorithm to map objects into points in  some k-dimensional space (k is user-defined), such that the dis-similarities are preserved. There are  two benefits from this mapping: ...
Indexing Multimedia Databases %28Tutorial%29.

Access Methods for Bi%2DTemporal Databases

Estimating the Selectivity of Spatial Queries Using the %60Correlation%27 Fractal Dimension.
We examine the estimation of selectivities for range and spatial join queries in real spatial databases. As we have shown earlier [FK94a], real point sets: (a) violate consistently the &#034;uniformity&#034; and &#034;independence&#034; assumptions, (b) can often be described as &#034;fractals&#034;, with non-integer (fractal) dimension. In this paper we show that, among the infinite family of fractal dimensions, the so called &#034;Correlation Dimension&#034; D 2 is the one that we need to predict the selectivity of spatial join. The main contribution is that, for all the real and synthetic point-sets we tried, the average number of neighbors for a given point of the point-set follows a power law, with D 2 as the exponent. This immediately solves the selectivity estimation for spatial joins, as well as for &#034;biased&#034; range queries (i.e., queries whose centers prefer areas of high point density). We present the formulas to estimate the selectivity for the biased queries, including an integration constant (K `shape  0  ) for ea...
Fast Searching by Content in Multimedia Databases.
A growing number of applications need access to video data stored in digital form on secondary storage devices (e.g., video-on-demand, multimedia messaging). As a result, video servers that are responsible for the storage and retrieval, at fixed rates, of hundreds of videos from disks are becoming increasingly important. Since video data tends to be voluminous, several disks are usually used in order to store the videos. A challenge is to devise schemes for the storage and retrieval of videos that distribute the workload evenly across disks, reduce the cost of the server and at the same time, provide good response times to client requests for video data. In this paper, we present schemes that are based on striping videos (fine-grained as well as coarse-grained) across disks in order to effectively utilize disk bandwidth. For the schemes, we show how an optimal-cost server architecture can be determined if data for a certain pre-specified number of videos is to be concurrently retrieved...
Flexible and Adaptable Buffer Management Techniques for Database Management Systems.
The problem of buffer management in database management systems is concerned with the efficient main memory allocation and management for answering database queries. Previous works on buffer allocation are based either exclusively on the availability of buffers at runtime or on the access patterns of queries. In this paper, we first propose a unified approach for buffer allocation in which both of these considerations are taken into account. Our approach is based on the notion of  marginal gains which specify the expected reduction in page faults by allocating extra buffers to a query. Then, we extend this approach to support adaptable buffer allocation. An adaptable buffer allocation algorithm automatically optimizes itself for the specific query workload. To achieve this adaptability, we propose using run-time information, such as the load of the system, in buffer allocation decisions. Our approach is to use a simple queueing model to predict whether a buffer allocation will improve ...


QBISM Extending a DBMS to Support 3D Medical Images.
this paper.  25 References  Adali S, Subrahmanian V S 1994 Amalgamating knowledge bases, II: Distributed mediators. International Journal of Intelligent and Cooperative Information Systems 3(4): 349-383  Arens Y, Knoblock C A, Shen W 1996 Query reformulation for dynamic information integration. In Wiederhold G (ed) Intelligent Integration of Information. Kluwer Academic Publishers: 11-42  Arya M, Cody W, Faloutsos C, Richardson J, Toga A 1994 QBISM: extending a DBMS to support 3D medical images. Proceedings of the loth International IEEE Conference on Data Engineering, Houston, Texas: 314-325  Batini C, Lenzerini M, Navathe S 1986 A comparative analysis of methodologies for database schema integration. ACM Computing Surveys 18(4): 3234:}4  Bayardo R, Bohrer W, Brice R, Cichocki A, Fowler G, Helal A, Kashyap V, Ksiezyk T, Martin G, Nodine M, Rashid M, Rusinkiewicz M, Shea R, Unnikrishnan C, Unmh A, Woelk D 1997 Semantic integration of information in open and dynamic environments. Proceedings of the 1997 ACM International Conference on the Management of Data (SIGMOD), Tucson: 195-206
Beyond Uniformity and Independence Analysis of R%2Dtrees Using the Concept of Fractal Dimension.
We propose the concept of fractal dimension of a set of points, in order to quantify the deviation from the uniformity distribution. Using measurements on real data sets (road intersections of U.S. counties, star coordinates from NASA&#039;s Infrared-Ultraviolet Explorer etc.) we provide evidence that real data indeed are skewed, and, moreover, we show that they behave as mathematical fractals, with a measurable, non-integer fractal dimension. Armed with this tool, we then show its practical use in predicting the performance of spatial access methods, and specifically of the R-trees. We provide the first analysis of R-trees for skewed distributions of points: We develop a formula that estimates the number of disk accesses for range queries, given only the fractal dimension of the point set, and its count. Experiments on real data sets show that the formula is very accurate: the relative error is usually below 5%, and it rarely exceeds 10%. We believe that the fractal dimension will help rep...
Fast Subsequence Matching in Time%2DSeries Databases.
We present an efficient indexing method to locate 1-dimensional subsequences witbin a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequence into a small set of multidimensional rectangles in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree [9]. In more deteil, we use a sliding window over the data sequence and extract its features; the result is a trail in feature space. We propose an efficient and effective algorithm to divide such trails into sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times. 
Quest A Project on Database Mining.

Hilbert R%2Dtree An Improved R%2Dtree using Fractals.
We propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in R-trees. This is done by proposing an ordering on the R-tree nodes. This ordering has to be &#039;good&#039;, in the sense that it should group &#039;similar&#039; data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19] we have chosen the so-called &#039;2D-c&#039; method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a welldefined set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. To the contrary, the R    -tree has no control over the space utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Hilbert R-tree. Our experiments show that the &#039;2-to-...
Efficient and Effective Querying by Image Content.
In the QBIC (Query By Image Content) project we are studying methods to query large  on-line image databases using the images&#039; content as the basis of the queries. Examples of  the content we use include color, texture, and shape of image objects and regions. Potential  applications include medical (&#034;Give me other images that contain a tumor with a texture like this  one&#034;), photo-journalism (&#034;Give me images that have blue at the top and red at the bottom&#034;),  and many others in art, fashion, cataloging, retailing, and industry.  We describe a set of novel features and similarity measures allowing query by color, texture,  and shape of image object. We demonstrate the effectiveness of the QBIC system with normalized  precision and recall experiments on test databases containing over 1000 images and 1000  objects populated from commercially available photo clip art images, and of images of airplane  silhouettes. We also consider the efficient indexing of these features, specifically addre...
The TV%2DTree An Index Structure for High%2DDimensional Data
We propose a file structure to index high-dimensionality data, typically, points in some feature space. The idea is to use only a few of the features, utilizing additional features whenever the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such `varying length&#039; feature vectors. Finally we report simulation results, comparing the proposed structure with the R    -tree, which is one of the most successful methods for low-dimensionality spaces. The results illustrate the superiority of our method, with up to 80% savings in disk accesses.  Type of Contribution: New Index Structure, for high-dimensionality feature spaces. Algorithms and performance measurements. Keywords: Spatial Index, Similarity Retrieval, Query by Content 1 Introduction  Many applications require enhanced indexing, capable of performing similarity searching on several, non-traditional (`exotic&#039;) data types. The targ...
On Packing R%2Dtrees.
We propose new R-tree packing techniques for static databases. Given a collection of rectangles, we sort them and we build the R-tree bottom-up. There are several ways to sort the rectangles; the innovation of this work is the use of fractals, and specifically the hilbert curve, to achieve better ordering of the rectangles and eventually better packing. We proposed and implemented several variations and performed experiments on synthetic, as well as real data (TIGER files from the U.S. Bureau of Census). The winning variation (`2D-c&#039;) was the one that sorts the rectangles according to the hilbert value of the center. This variation consistently outperforms the packing method of Roussopoulos and Leifker [24], as well as other R-tree variants. The performance gain of the our method seems to increase with the skeweness of the data distribution; specifically, on the (highly skewed) TIGER dataset, it achieves up to 58% improvement in response time over the older packing algorithm and 36% ov...
Efficient Similarity Search In Sequence Databases.
. We propose an indexing method for time sequences for processing similarity queries. We use the Discrete Fourier Transform (DFT) to map time sequences to the frequency domain, the crucial observation being that, for most sequences of practical interest, only the first few frequencies are strong. Another important observation is Parseval&#039;s theorem, which specifies that the Fourier transform preserves the Euclidean distance in the time or frequency domain. Having thus mapped sequences to a lowerdimensionality space by using only the first few Fourier coefficients, we use R    - trees to index the sequences and efficiently answer similarity queries. We provide experimental results which show that our method is superior to search based on sequential scanning. Our experiments show that a few coefficients (1-3) are adequate to provide good performance. The performance gain of our method increases with the number and length of sequences.   On sabbatical from the Dept. of Computer Science, Un...
Declustering Using Fractals.
We propose a method to achieve declustering for cartesian product files on M units. The focus is on range queries, as opposed to partial match queries that older declustering methods have examined. Our method uses a distance-preserving mapping, namely, the Hilbert curve, to impose a linear ordering on the multidimensional points (buckets); then, it traverses the buckets according to this ordering, assigning buckets to disks in a round-robin fashion. Thanks to the good distance-preserving properties of the Hilbert curve, the end result is that each disk contains buckets that are far away in the linear ordering, and, most probably, far away in the k-d address space. This is exactly the goal of declustering. Experiments show that these intuitive arguments lead indeed to good performance: the proposed method performs at least as well or better than older declustering schemes. Categories and Subject Descriptors: E.1 [Data Structures]; E.5 [Files]; H.2.2 [Data Base Management]: Physical Des...
The QBIC Project Querying Images by Content%2C Using Color%2C Texture%2C and Shape.
bonell, and T. M. Mitchell, editors, Machine Learning, volume 1. Margan Kaufmann Publishers, Inc., 1983.  [16] Niblack, Wayne, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin. The qbic project: Querying images by content using color, texture, and shape. In Storage and Retrieval for Images and Video Databases, SPIE, volume 1908, 1993.  [17] C. E. Shannon and W. Weaver. The Mathematical Theory of Communication. University of Illinois Press, Urbana, Ill, 1964.  29  References  
QBISM A Prototype 3%2DD Medical Image Database System.
this paper. However, these automatic or semi-automatic warping algorithms are extremely important for this application. It is precisely this technology that permits anatomic structure-based access to acquired medical images as well as comparisons among studies, even of different patients, as long as they have been warped to the same atlas. Furthermore, it enables the database to grow, and be queryable, without time-consuming manual segmentation of the data.
High Performance R%2Dtrees.

Hybrid Index Organizations for Text Databases.

Parallel R%2Dtrees.
We consider the problem of exploiting parallelism to accelerate the performance of spatial access methods and specifically, R-trees [11]. Our goal is to design a server for spatial data, so that to maximize the throughput of range queries. This can be achieved by (a) maximizing parallelism for large range queries, and (b) by engaging as few disks as possible on point queries [22]. We propose a simple hardware architecture consisting of one processor with several disks attached to it. On this architecture, we propose to distribute the nodes of a traditional R-tree, with cross-disk pointers (`Multiplexed&#039; R-tree). The R-tree code is identical to the one for a single-disk R-tree, with the only addition that we have to decide which disk a newly created R-tree node should be stored in. We propose and examine several criteria to choose a disk for a new node. The most successful one, termed `proximity index&#039; or PI, estimates the similarity of the new node with the other R-tree nodes already o...
On B%2DTree Indices for Skewed Distributions.
It is often the case that the set of values over which a B-Tree is constructed has a skewed distribution. We present a geometric growth technique to manage postings records in such cases, and show that the performance of such a technique is better than that of a straightforward fixed length postings list: It guarantees 1 disk access on searching, and it takes a fraction of the space that its competitor requires (55 % to 66%, in our experiments). 1.
Signature Files.
This paper deals with the estimation of the signature weight as generated by the superimposed coding technique adopted in &#034;multiple&#034;   signature files. The estimation is needed for performance evaluation of such organizations used for information retrieval applications. In particular, simple formulas for the probability density function, the expected value and the variance of the signature weight are presented. The presented formulas can be derived following a general methodology we called the   - transform approach in a previous work, which results much more simple than the method used by other authors for the derivation of the density function. Equivalence of the results is also shown.
Frame%2DSliced Signature Files.
this paper we provide two example cases for this purpose and study the performance of IFD in the conventional sequential signature file (SSF) method and a new vertical partitioning environment, the multiframe signature file (MFSF) method, that we introduced in our recent study [10, 11, 18]. For this purpose we developed a test environment and implemented the SSF and MFSF methods. We extended these methods to use IFD and tested their performance with real data. The experiments show that IFD improves the performance of the inspected methods by reducing the observed FD and the (query) response time. (Further experiments with similar results involving a generalized frame sliced signature file approach are reported in Kocberber [18].)  The organization of the paper is as follows. In Section 2, the conventional FD estimation method and the proposed FD estimation method, IFD, are explained. Section 3 explains the test environment used in the experiments. In Sections 4 and 5, we apply IFD to the SSF and MFSF methods, respectively, and measure the performance improvements obtained by IFD experimentally with real data. Section 6 provides the conclusion. In the Appendix we provide a formal proof which shows that under certain conditions the number of false drop records (FD) estimated by considering the average number of terms in the records is less than or equal to the FD estimated by considering individual D values of the records
Analytical results on the quadtree decomposition of arbitrary rectangles.

DOT A Spatial Access Method Using Fractals.
Existing Database Management Systems (DBMSs) do not handle efficiently multi-dimensional data such as boxes, polygons, or even points in a multi-dimensional space. We examine access methods for these data with two design goals in mind: (a) efficiency in terms of search speed and space overhead and (b) ability to be integrated in a DBMS easily. We propose a method to map multidimensional objects into points in a 1-dimensional space; thus, traditional primary-key access methods can be applied, with very few extensions on the part of the DBMS. We propose such mappings based on fractals; we implemented the whole method on top of a B +-tree, along with several mappings. Simulation experiments on several distributions of the input data show
Flexible Buffer Allocation Based on Marginal Gains.

Predictive Load Control for Flexible Buffer Allocation.

Disk Allocation Methods Using Error Correcting Codes.

An Architecture for High Performance Engineering Information Systems.

Incorporating String Search in a Hypertext System User Interface and Signature File Design Issues.
: Hypertext systems provide an appealing mechanism for informally browsing databases by traversing selectable links. However, in many fact finding situations string search is an effective complement to browsing. This paper describes the application of the signature file method to achieve rapid and convenient string search in small personal computer hypertext environments. The method has been implemented in a prototype, as well as in a commercial product. Performance data for search times and storage space are presented from a commercial hypertext database. User interface issues are then discussed. Experience with the string search interface indicates that it was used sucessfully by novice users. Address correspondence to: Christos Faloutsos Computer Science Department, University of Maryland, College Park, MD 20742, USA Tel: 1 (301) 454-1462 -- Fax: 1 (301) 454-8346 -- Email: christos@cs.umd.edu 1  Introduction  Early exploratory hypertext systems are giving way to numerous commercial...
Analysis for the End of Block Wasted Space.

Incorporating String Search in a Hypertext System User Interface and Signature File Design Issues.
: Hypertext systems provide an appealing mechanism for informally browsing databases by traversing selectable links. However, in many fact finding situations string search is an effective complement to browsing. This paper describes the application of the signature file method to achieve rapid and convenient string search in small personal computer hypertext environments. The method has been implemented in a prototype, as well as in a commercial product. Performance data for search times and storage space are presented from a commercial hypertext database. User interface issues are then discussed. Experience with the string search interface indicates that it was used sucessfully by novice users. Address correspondence to: Christos Faloutsos Computer Science Department, University of Maryland, College Park, MD 20742, USA Tel: 1 (301) 454-1462 -- Fax: 1 (301) 454-8346 -- Email: christos@cs.umd.edu 1  Introduction  Early exploratory hypertext systems are giving way to numerous commercial...
Signature%2DBased Text Retrieval Methods A Survey.
gure interpretation method. In 9th Int. Conference
Fractals for Secondary Key Retrieval.
In this paper we propose the use of fractals and especially the Hilbert curve, in order to design good distance-preserving mappings. Such mappings improve the performance of secondary-key- and spatial- access methods, where multi-dimensional points have to be stored on an 1-dimensional medium (e.g., disk). Good clustering reduces the number of disk accesses on retrieval, improving the response time. Our experiments on range queries and nearest neighbor queries showed that the proposed Hilbert curve achieves better clustering than older methods (&#034;bit-shuffling&#034;, or Peano curve), for every situation we tried.  Categories and Subject Descriptors: H.2.2 [Database Management]: Physical Design-access  methods; H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing-indexing  methods  General Terms: Algorithms, Design, Performance  Additional Keywords: distance preserving mappings, geometric data. 1. INTRODUCTION  In this work we propose some space-filling curves which achiev...
Declustering Using Error Correcting Codes.

Performance Issues in the Binary Relationship Model.

Tri%2Dcell%2Da data structure for spatial objects.

Fast Text Access Methods for Optical and Large Magnetic Disks Designs and Performance Comparison.

Signature Files An Integrated Access Method for Text and Attributes

Expert Database Systems Efficient Support for Engineering Environments.

Gray Codes for Partial Match and Range Queries.

An Efficient Pictorial Database System for PSQL.
Computer vision offers a number of techniques that can be used in the context of pictorial information systems. To motivate this point of view, we first present the basic issues involved in computer vision and in multimedia information systems, and emphasize the differences between these domains. We then outline the contributions that computer vision can make to the development of efficient multimedia information systems, especially for handling queries by visual example (QVE). In the second part of the paper, we concentrate on the matters of archiving and retrieving images from large databases, in the case of QVE. An approach is proposed that relies on two concepts, namely relevance and focusof -attention. These mechanisms allow to locate and select the most pertinent information from images. They can be used at the image archival stage, to automatically determine which parts of the image should provide meaningful indices to be compiled into the image access tables. Relevance and focu...
Analysis of Object Oriented Spatial Access Methods.

The R %2DTree A Dynamic Index for Multi%2DDimensional Objects.
The problem of indexing multidimensional objects is considered. First, a classification of existing methods is given along with a discussion of the major issues involved in multidimensional data indexing. Second, a variation to Guttman&#039;s R-trees (R -trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced. Algorithms for searching, updating, initial packing and reorganization of the structure are discussed in detail. Finally, we provide analytical results indicating that R -trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles. 1 Also with University of Maryland Systems Research Center. 2 Also with University of Maryland Institute for Advanced Computer Studies (UMIACS). This research was sponsored partialy by the National Science Foundation under Grant CDR-85-00108. 1. Introduction It has been recognized in the past that existing Database Management Systems (DBMSs) do not ...
Optimal Signature Extraction and Information Loss.

Description and Performance Analysis of Signature File Methods for Office Filing.

Multiattribute Hashing Using Gray Codes.
[36] Timos Sellis, Nick Roussopoulos, and Christos Faloutsos. The R+-tree: A dynamic index for
Design and Performance Considerations for an Optical Disk%2DBased Multimedia Object Server.

Signature files Design and Performance Comparison of Some Signature Extraction Methods.

Design of a Signature File Method that Accounts for Non%2DUniform Occurrence and Query Frequencies.

Access Methods for Text.

Signature Files An Access Method for Documents and Its Analytical Performance Evaluation.

Design Considerations for a Message File Server.

A Multimedia Office Filing System.

Performance Considerations in Message Files.

